QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#378653 | #8568. Expected Diameter | ucup-team1004# | AC ✓ | 12898ms | 129716kb | C++14 | 1.8kb | 2024-04-06 14:02:25 | 2024-04-06 14:02:25 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=2010,mod=998244353,M=N;
typedef long long ll;
ll fastpow(ll a,int b)
{
ll s=1;
for(;b;b>>=1,a=a*a%mod)
if(b&1) s=s*a%mod;
return s;
}
ll fac[N],ifac[N],inv[N];
int n,p1,p2;
ll g1[M][N],g2[M][N],f[M][N],h[M][N];
void init(int n)
{
fac[0]=ifac[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
ifac[n]=fastpow(fac[n],mod-2);
for(int i=n-1;i;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
for(int i=1;i<=n;i++) inv[i]=fac[i-1]*ifac[i]%mod;
}
ll s[N];
void exp(ll *a)
{
for(int i=0;i<=n;i++) s[i]=(i==0);
for(int i=1;i<=n;i++) a[i]=a[i]*i%mod;
for(int i=1;i<=n;i++)
{
for(int j=0;j<i;j++)
s[i]=(s[i]+s[j]*a[i-j])%mod;
s[i]=s[i]*inv[i]%mod;
}
for(int i=0;i<=n;i++) a[i]=s[i];
}
int main()
{
ll p1,p2;
scanf("%d%lld%lld",&n,&p1,&p2);
p1=p1*fastpow(p2,mod-2)%mod;
p2=(mod+1-p1)%mod;
if(n==1) return puts("0"),0;
init(n+1);
f[0][1]=h[0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<n;j++) h[i][j]=(f[i-1][j]*p1+(i==1?0:f[i-2][j]*p2))%mod;
exp(h[i]);
for(int j=1;j<=n;j++) f[i][j]=h[i][j-1];
}
for(int i=0;i<=n;i++)
for(int j=1;j<n;j++)
g1[i][j]=(f[i][j]-(i==0?0:f[i-1][j])+mod)%mod;
for(int i=1;i<=n;i++)
for(int j=1;j<n;j++)
g2[i][j]=(g1[i-1][j]*p1+(i==1?0:g1[i-2][j]*p2))%mod;
ll ans=0;
for(int i=1;i<=n;i++)
{
ll cur=h[i][n-1]-h[i-1][n-1]+mod;
for(int j=1;j<n;j++)
cur=(cur+(mod-g2[i][j])*h[i-1][n-j-1])%mod;
cur=cur*fac[n]%mod;
ans=(ans+cur*i*2)%mod;
}
for(int i=0;i<=n;i++)
for(int j=1;j<n;j++)
{
ll s1=g1[i][j]*g1[i][n-j]%mod*inv[2]%mod*fac[n]%mod,
s2=g1[i][j]*g1[i+1][n-j]%mod*fac[n]%mod;
ans=(ans+(p1*(2*i+1)+p2*(2*i+2))%mod*s1+p2*(2*i+3)%mod*s2)%mod;
}
printf("%lld\n",ans*fastpow(n,(mod-1)-(n-2))%mod);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 6008kb
input:
2 1 3
output:
665496237
result:
ok 1 number(s): "665496237"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5912kb
input:
3 2 3
output:
665496238
result:
ok 1 number(s): "665496238"
Test #3:
score: 0
Accepted
time: 12895ms
memory: 129716kb
input:
2000 1 2
output:
254870088
result:
ok 1 number(s): "254870088"
Test #4:
score: 0
Accepted
time: 12898ms
memory: 129664kb
input:
2000 1 3
output:
193693601
result:
ok 1 number(s): "193693601"
Test #5:
score: 0
Accepted
time: 12868ms
memory: 129568kb
input:
1999 188 211
output:
463395288
result:
ok 1 number(s): "463395288"
Test #6:
score: 0
Accepted
time: 12708ms
memory: 128980kb
input:
1990 470 818
output:
479264654
result:
ok 1 number(s): "479264654"
Test #7:
score: 0
Accepted
time: 1624ms
memory: 52624kb
input:
1000 407 783
output:
20089106
result:
ok 1 number(s): "20089106"
Test #8:
score: 0
Accepted
time: 1576ms
memory: 51520kb
input:
990 884 901
output:
94051884
result:
ok 1 number(s): "94051884"
Test #9:
score: 0
Accepted
time: 1578ms
memory: 52504kb
input:
995 873 988
output:
209191626
result:
ok 1 number(s): "209191626"
Test #10:
score: 0
Accepted
time: 197ms
memory: 21140kb
input:
500 307 938
output:
603465152
result:
ok 1 number(s): "603465152"
Test #11:
score: 0
Accepted
time: 192ms
memory: 20464kb
input:
490 237 732
output:
402554558
result:
ok 1 number(s): "402554558"
Test #12:
score: 0
Accepted
time: 198ms
memory: 20820kb
input:
495 473 511
output:
833418554
result:
ok 1 number(s): "833418554"
Test #13:
score: 0
Accepted
time: 28ms
memory: 11588kb
input:
250 69 207
output:
786182422
result:
ok 1 number(s): "786182422"
Test #14:
score: 0
Accepted
time: 21ms
memory: 11380kb
input:
240 184 259
output:
473414786
result:
ok 1 number(s): "473414786"
Test #15:
score: 0
Accepted
time: 23ms
memory: 11592kb
input:
245 478 807
output:
312847415
result:
ok 1 number(s): "312847415"
Test #16:
score: 0
Accepted
time: 5ms
memory: 8204kb
input:
125 112 253
output:
31497383
result:
ok 1 number(s): "31497383"
Test #17:
score: 0
Accepted
time: 4ms
memory: 8200kb
input:
120 137 498
output:
923043504
result:
ok 1 number(s): "923043504"
Test #18:
score: 0
Accepted
time: 0ms
memory: 7316kb
input:
100 230 792
output:
203877027
result:
ok 1 number(s): "203877027"
Extra Test:
score: 0
Extra Test Passed