QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#378653#8568. Expected Diameterucup-team1004#AC ✓12898ms129716kbC++141.8kb2024-04-06 14:02:252024-04-06 14:02:25

Judging History

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

  • [2024-04-06 14:02:25]
  • 评测
  • 测评结果:AC
  • 用时:12898ms
  • 内存:129716kb
  • [2024-04-06 14:02:25]
  • 提交

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