UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#204748#3626. 概率计算drdilyor100600ms9064kbC++994b2024-06-09 09:11:582024-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