ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#204748 | #3626. 概率计算 | drdilyor | 100 | 600ms | 9064kb | C++ | 994b | 2024-06-09 09:11:58 | 2024-06-09 12:01:52 |
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,p,q;
const int mod=1e9+7;
int dp[500005];
int coef[500005];
int qkp(int b,int p){
int r=1;
while(p){
if(p&1)(r*=b)%=mod;
p/=2;
(b*=b)%=mod;
}
return r;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>p>>q;
p=q-p+mod,p%=mod;
memset(dp,-1,sizeof(dp));
dp[n]=1;
dp[0]=0;
coef[1]=(q-p+mod)*qkp(q,mod-2)%mod;
int d=p*qkp(q,mod-2)%mod;
for(int i=2;i<n;i++){
coef[i]=(q-p+mod)*qkp(q,mod-2)%mod*qkp(mod+1-d*coef[i-1]%mod+mod,mod-2)%mod;
//dp[i]=coef[i]*dp[i+1]
//dp[i]*(1-(p/q)*coef[i-1])=dp[i+1]*(q-p)/q
//dp[1]=dp[2]*((q-p)/q)
//dp[2]=dp[1]*(p/q)+dp[3]*((q-p)/q)
//dp[3]
//dp[i]=dp[i-1]*((q-p)/q)+dp[i+1]*p/q
}
for(int i=n-1;i>=1;i--){
dp[i]=dp[i+1]*coef[i]%mod;
}
for(int i=1;i<=n;i++)cout<<dp[i]<<" ";
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 5156kb
input:
2 973073937 999758391
output:
382714835 1
result:
ok single line: '382714835 1 '
Test #2:
score: 10
Accepted
time: 0ms
memory: 5156kb
input:
3 365477961 916551500
output:
502567110 284127562 1
result:
ok single line: '502567110 284127562 1 '
Test #3:
score: 10
Accepted
time: 0ms
memory: 5160kb
input:
299 1 2
output:
441471575 882943150 324414718 765886293 207357861 648829436 90301004 531772579 973244154 414715722 8...
result:
ok single line: '441471575 882943150 324414718 ...75585290 117056858 558528433 1 '
Test #4:
score: 10
Accepted
time: 0ms
memory: 5160kb
input:
298 1 2
output:
265100673 530201346 795302019 60402685 325503358 590604031 855704704 120805370 385906043 651006716 9...
result:
ok single line: '265100673 530201346 795302019 ...04697989 469798662 734899335 1 '
Test #5:
score: 10
Accepted
time: 0ms
memory: 5160kb
input:
300 753850787 766896585
output:
759172300 794989483 298082840 772416102 992992517 498473273 537468571 717895255 309938428 87710480 9...
result:
ok single line: '759172300 794989483 298082840 ...95226663 968970710 101445994 1 '
Test #6:
score: 10
Accepted
time: 4ms
memory: 5156kb
input:
299 847729699 865235904
output:
536954675 858661352 666905805 760056224 731385885 488079853 900124555 517448601 469188960 640714011 ...
result:
ok single line: '536954675 858661352 666905805 ...08832697 731788147 203623632 1 '
Test #7:
score: 10
Accepted
time: 0ms
memory: 5160kb
input:
298 803230088 887298490
output:
254886050 166570397 615685083 699726315 907262083 835292727 887332047 755218278 128129081 285779446 ...
result:
ok single line: '254886050 166570397 615685083 ...82582015 739421450 896169531 1 '
Test #8:
score: 10
Accepted
time: 206ms
memory: 9060kb
input:
500000 242253657 742311700
output:
873056060 153147128 516367397 745999010 682815667 668319169 546803226 971263033 492810120 522516088 ...
result:
ok single line: '873056060 153147128 516367397 ...78641368 472470703 156125084 1 '
Test #9:
score: 10
Accepted
time: 202ms
memory: 9064kb
input:
499999 926824122 947703016
output:
97940792 372292291 473100395 112083731 331585835 161720951 797940017 450127708 625687708 173690184 5...
result:
ok single line: '97940792 372292291 473100395 1...72230663 307607479 939929919 1 '
Test #10:
score: 10
Accepted
time: 188ms
memory: 9060kb
input:
499998 534420093 818113917
output:
71495630 454243883 745549062 513163061 178770645 773603674 424486391 655895470 527258923 484527216 8...
result:
ok single line: '71495630 454243883 745549062 5...47262765 178322731 104130412 1 '
Extra Test:
score: 0
Extra Test Passed