QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#381943 | #8568. Expected Diameter | ucup-team004# | AC ✓ | 12397ms | 98024kb | C++20 | 3.1kb | 2024-04-07 22:21:11 | 2024-04-07 22:21:12 |
Judging History
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