QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#54500#1084. Beautiful Sequence UnravelingtricyzhkxAC ✓238ms6944kbC++141.5kb2022-10-09 08:15:282022-10-09 08:15:31

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-09 08:15:31]
  • Judged
  • Verdict: AC
  • Time: 238ms
  • Memory: 6944kb
  • [2022-10-09 08:15:28]
  • Submitted

answer

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;
struct Fastmod
{
	int m;ll b;
	void init(int _m){m=_m;b=((lll)1<<64)/m;}
	int operator()(ll a)
	{
		ll q=((lll)a*b)>>64;a-=q*m;
		return a>=m?a-m:a;
	}
}Mod;
int mod,C[410][410],pw[410][410],ipw[410][410],f[410][410],g[410],sum[410][410];
int add(int a,int b){return (a+=b)>=mod?a-mod:a;}
int mul(int a,int b){return Mod((ll)a*b);}
int power(int a,int b)
{
	int ans=1;
	for(;b;b>>=1,a=mul(a,a))
		if(b&1) ans=mul(ans,a);
	return ans;
}
int main()
{
	int n,K,ans=0;
	cin>>n>>K>>mod;Mod.init(mod);
	for(int i=1;i<=n;i++)
	{
		pw[0][i]=ipw[0][i]=1;
		int iv=power(i,mod-2);
		for(int j=1;j<=n;j++)
			pw[j][i]=mul(pw[j-1][i],i),
			ipw[j][i]=mul(ipw[j-1][i],iv);
	}
	for(int i=0;i<=n;i++) C[i][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++)
			C[i][j]=add(C[i-1][j-1],C[i-1][j]);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			f[i][j]=pw[i][j];
			for(int l=1;l<=j;l++)
				f[i][j]=Mod(f[i][j]+(ll)(mod-pw[i][l])*sum[l][j-l+1]+
				(ll)pw[i][l-1]*sum[l-1][j-l+1]+(ll)pw[i][l]*sum[l][j-l]+
				(ll)(mod-pw[i][l-1])*sum[l-1][j-l]);
		}
		for(int l=1;l<=n;l++)
			for(int j=1;j<=n;j++)
				sum[l][j]=Mod(sum[l][j]+(ll)f[i][j]*ipw[i][l]);
	}
	for(int i=1;i<=n;i++) g[i]=f[n][i];
	for(int i=n;i>=1;i--)
		for(int j=1;j<i;j++)
			g[i]=Mod(g[i]+(ll)((i-j)&1?mod-C[i][j]:C[i][j])*g[j]);
	for(int i=1,c=K;i<=n;i++)
	{
		ans=Mod(ans+(ll)c*g[i]);
		c=mul(mul(c,K-i),power(i+1,mod-2));
	}
	cout<<ans<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 5576kb

input:

2 2 1000000007

output:

2

result:

ok 1 number(s): "2"

Test #2:

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

input:

3 4 1000000009

output:

36

result:

ok 1 number(s): "36"

Test #3:

score: 0
Accepted
time: 45ms
memory: 6376kb

input:

228 112263 998244353

output:

379700769

result:

ok 1 number(s): "379700769"

Test #4:

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

input:

1 1 998595277

output:

1

result:

ok 1 number(s): "1"

Test #5:

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

input:

2 2 998683811

output:

2

result:

ok 1 number(s): "2"

Test #6:

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

input:

3 1 998277223

output:

0

result:

ok 1 number(s): "0"

Test #7:

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

input:

4 1 998365733

output:

0

result:

ok 1 number(s): "0"

Test #8:

score: 0
Accepted
time: 234ms
memory: 6920kb

input:

400 100000000 998244353

output:

318973800

result:

ok 1 number(s): "318973800"

Test #9:

score: 0
Accepted
time: 237ms
memory: 6692kb

input:

400 1 1000000007

output:

0

result:

ok 1 number(s): "0"

Test #10:

score: 0
Accepted
time: 3ms
memory: 5668kb

input:

2 9 999603883

output:

72

result:

ok 1 number(s): "72"

Test #11:

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

input:

1 1 998784541

output:

1

result:

ok 1 number(s): "1"

Test #12:

score: 0
Accepted
time: 3ms
memory: 5680kb

input:

3 3 999209353

output:

12

result:

ok 1 number(s): "12"

Test #13:

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

input:

4 12 999787531

output:

16544

result:

ok 1 number(s): "16544"

Test #14:

score: 0
Accepted
time: 228ms
memory: 6768kb

input:

400 3 998785127

output:

505031599

result:

ok 1 number(s): "505031599"

Test #15:

score: 0
Accepted
time: 229ms
memory: 6880kb

input:

400 77 999400643

output:

877578741

result:

ok 1 number(s): "877578741"

Test #16:

score: 0
Accepted
time: 238ms
memory: 6708kb

input:

400 374 998458939

output:

202865317

result:

ok 1 number(s): "202865317"

Test #17:

score: 0
Accepted
time: 230ms
memory: 6888kb

input:

400 77435643 999245677

output:

833344996

result:

ok 1 number(s): "833344996"

Test #18:

score: 0
Accepted
time: 234ms
memory: 6896kb

input:

399 72119824 999010279

output:

188282648

result:

ok 1 number(s): "188282648"

Test #19:

score: 0
Accepted
time: 224ms
memory: 6944kb

input:

398 22521432 999827603

output:

986913334

result:

ok 1 number(s): "986913334"

Test #20:

score: 0
Accepted
time: 231ms
memory: 6816kb

input:

397 77955743 998803427

output:

32764673

result:

ok 1 number(s): "32764673"