QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#381943#8568. Expected Diameterucup-team004#AC ✓12397ms98024kbC++203.1kb2024-04-07 22:21:112024-04-07 22:21:12

Judging History

你现在查看的是最新测评结果

  • [2024-04-07 22:21:12]
  • 评测
  • 测评结果:AC
  • 用时:12397ms
  • 内存:98024kb
  • [2024-04-07 22:21:11]
  • 提交

answer

#include <bits/stdc++.h>

using ll = unsigned long long;

using namespace std;
#define For(i,l,r) for(int i=l;i<=(int)(r);i++)
#define Rep(i,r,l) for(int i=r;i>=(int)(l);i--)
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define PI pair<int,int>
const int N=2005,mod=998244353;
const ll mod2=(ll)mod*mod*15;
ll ksm(ll a,int b){
    int ans=1;
    for(;b;b>>=1){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
    }
    return ans;
}
ll n,c[N][N],fac[N],ni[N],dp[N][N],f[N],x,y,p1,p2;
inline void add(ll &a,ll b){
 //   a=(a+b)%mod;
    a+=b; if(a>=mod2)a-=mod2;
}
inline ll ask(int i,int d){
    if(d<0)return 0;
    if(d>n)return 0;
    return dp[i][d]+(d?mod-dp[i][d-1]:0);
}
 ll tmp1[N],tmp2[N];
 ll ASK[N][N];
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T=1;
    while(T--){
        cin>>n;cin>>x>>y;
        //n=100; x=233; y=666;
        if(n==1){
            cout<<0<<endl; exit(0);
        }
        p1=x*ksm(y,mod-2)%mod;
        p2=(mod+1-p1)%mod;
        For(i,0,n)For(j,c[i][0]=1,i)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
        For(i,fac[0]=1,n)fac[i]=fac[i-1]*i%mod;
        Rep(i,n,0)ni[i]=ksm(fac[i],mod-2);
        For(i,0,n)dp[1][i]=1;
        For(j,1,n){
            For(i,1,n){tmp1[i]=dp[i][j-1]*ni[i-1]%mod*i%mod; tmp2[i]=j>=2?dp[i][j-2]*ni[i-1]%mod*i%mod:0;}
            For(i,1,n){
                dp[i][j]=dp[i][j]%mod*(i>=2?fac[i-2]:1)%mod;
                ll dp1=dp[i][j]*p1%mod*ni[i-1]%mod;
                ll dp2=dp[i][j]*p2%mod*ni[i-1]%mod;
                For(k,1,n-i){
                    add(dp[i+k][j],dp1*tmp1[k]);
                    if(j>=2)add(dp[i+k][j],dp2*tmp2[k]);
                }
               // cerr<<dp[i][j]<<" i:"<<i<<" j:"<<j<<endl;
            }
        }
        For(i,1,n)
            For(j,0,n)
                dp[i][j]=dp[i][j]*i%mod;
        //cerr<<clock()<<endl;return 0;
        ll ans=0;
        For(i,0,n)For(j,0,n)ASK[i][j]=(ask(i,j-1)*p1+ask(i,j-2)*p2)%mod;
        For(j,1,n){
            memset(f,0,sizeof(f));
            f[0]=1;
            For(i,1,n){
                For(k,1,i){
                    add(f[i],f[i-k]*ASK[k][j]%mod*c[i-1][k-1]);
                }
                f[i]%=mod;
            }
            For(i,1,n){
                ll u=ASK[i][j];
                ll w=(f[i]+(mod-u))%mod;
                add(ans,w*(j?dp[n-i][j-1]:0)%mod*c[n][i]%mod*(j*2));
            }
        }
        //cerr<<ans<<endl;
        For(d,0,n){
            For(i,1,n){
                add(ans,ask(i,d)*ask(n-i,d)%mod*c[n-1][i-1]%mod*p1%mod*(2*d+1));
                add(ans,ask(i,d)*ask(n-i,d)%mod*c[n-1][i-1]%mod*p2%mod*(2*d+2));
                add(ans,ask(i,d)*ask(n-i,d+1)%mod*c[n][i]%mod*p2%mod*(2*d+3));
            }
        }
        cout<<ans%mod*ksm(ksm(n,n-2),mod-2)%mod<<endl;
        cerr<<clock()<<endl;
    }
    return 0;
}
/*
3 2 3                            
332748119 i:2 j:1
2 i:2 j:2
2 i:2 j:3
665496238 i:3 j:1
665496244 i:3 j:2
332748129 i:3 j:3
665496238
887328316
*/

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 7844kb

input:

2 1 3

output:

665496237

result:

ok 1 number(s): "665496237"

Test #2:

score: 0
Accepted
time: 1ms
memory: 7764kb

input:

3 2 3

output:

665496238

result:

ok 1 number(s): "665496238"

Test #3:

score: 0
Accepted
time: 12397ms
memory: 98024kb

input:

2000 1 2

output:

254870088

result:

ok 1 number(s): "254870088"

Test #4:

score: 0
Accepted
time: 12175ms
memory: 97960kb

input:

2000 1 3

output:

193693601

result:

ok 1 number(s): "193693601"

Test #5:

score: 0
Accepted
time: 12132ms
memory: 97888kb

input:

1999 188 211

output:

463395288

result:

ok 1 number(s): "463395288"

Test #6:

score: 0
Accepted
time: 12071ms
memory: 97740kb

input:

1990 470 818

output:

479264654

result:

ok 1 number(s): "479264654"

Test #7:

score: 0
Accepted
time: 1479ms
memory: 51416kb

input:

1000 407 783

output:

20089106

result:

ok 1 number(s): "20089106"

Test #8:

score: 0
Accepted
time: 1431ms
memory: 49120kb

input:

990 884 901

output:

94051884

result:

ok 1 number(s): "94051884"

Test #9:

score: 0
Accepted
time: 1481ms
memory: 50940kb

input:

995 873 988

output:

209191626

result:

ok 1 number(s): "209191626"

Test #10:

score: 0
Accepted
time: 180ms
memory: 27436kb

input:

500 307 938

output:

603465152

result:

ok 1 number(s): "603465152"

Test #11:

score: 0
Accepted
time: 175ms
memory: 26372kb

input:

490 237 732

output:

402554558

result:

ok 1 number(s): "402554558"

Test #12:

score: 0
Accepted
time: 178ms
memory: 27456kb

input:

495 473 511

output:

833418554

result:

ok 1 number(s): "833418554"

Test #13:

score: 0
Accepted
time: 23ms
memory: 19056kb

input:

250 69 207

output:

786182422

result:

ok 1 number(s): "786182422"

Test #14:

score: 0
Accepted
time: 24ms
memory: 16876kb

input:

240 184 259

output:

473414786

result:

ok 1 number(s): "473414786"

Test #15:

score: 0
Accepted
time: 26ms
memory: 17672kb

input:

245 478 807

output:

312847415

result:

ok 1 number(s): "312847415"

Test #16:

score: 0
Accepted
time: 2ms
memory: 12840kb

input:

125 112 253

output:

31497383

result:

ok 1 number(s): "31497383"

Test #17:

score: 0
Accepted
time: 2ms
memory: 10628kb

input:

120 137 498

output:

923043504

result:

ok 1 number(s): "923043504"

Test #18:

score: 0
Accepted
time: 0ms
memory: 11988kb

input:

100 230 792

output:

203877027

result:

ok 1 number(s): "203877027"

Extra Test:

score: 0
Extra Test Passed