QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#889503#1084. Beautiful Sequence UnravelingKangliyangAC ✓743ms13644kbC++142.1kb2025-02-08 16:18:542025-02-08 16:18:58

Judging History

This is the latest submission verdict.

  • [2025-02-08 16:18:58]
  • Judged
  • Verdict: AC
  • Time: 743ms
  • Memory: 13644kb
  • [2025-02-08 16:18:54]
  • Submitted

answer

#include <bits/stdc++.h>
#define in(x) freopen(#x".in","r",stdin)
#define out(x) freopen(#x".out","w",stdout)
#define make(x) freopen(#x".in","w",stdout)
#define ll long long
#define int long long
#ifdef MY_COMPUTER
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
#define vector basic_string
#define pii array<int,2>

using namespace std;

inline int read()
{
	int s=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*f;
}
template<typename _it>
void read(_it a,_it b){
	while(a!=b) (*a)=read(),a++;
}
template<typename _it>
void write(const char* form,_it a,_it b,int op=0){
	while(a!=b) printf(form,*a),a++;
	if(op) puts("");
}
int n,m,mod,f[510][510],sum[510][510],pw[510][510],ipw[510][510],C[510][510],ans,g[510];
//sum[t][j]:\sum f[i][j]/t^i
int power(int a,int b){
	int ans=1;
	while(b){
		if(b&1) ans=ans*a%mod;
		a=a*a%mod,b>>=1;
	}
	return ans;
}
signed main()
{
	//ios::sync_with_stdio(false);
	n=read(),m=read(),mod=read();
	C[0][0]=1;
	for(int i=1,ii;i<=n;i++){
		ii=power(i,mod-2),C[i][0]=1;
		pw[i][0]=ipw[i][0]=1;
		for(int j=1;j<=n;j++){
			pw[i][j]=pw[i][j-1]*i%mod;
			ipw[i][j]=ipw[i][j-1]*ii%mod;
		}
		for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			f[i][j]=pw[j][i];
			for(int t=1;t<=j;t++){
				f[i][j]-=pw[t][i]*sum[t][j-t+1]%mod;
				f[i][j]+=pw[t][i]*sum[t][j-t]%mod;
				f[i][j]+=pw[t-1][i]*sum[t-1][j-t+1]%mod;
				f[i][j]-=pw[t-1][i]*sum[t-1][j-t]%mod;
				f[i][j]=(f[i][j]%mod+mod)%mod;
			}
		}
		for(int j=1;j<=n;j++)
			for(int t=1;t<=n;t++)
				sum[t][j]=(sum[t][j]+f[i][j]*ipw[t][i])%mod;//,printf("%lld %lld add %lld\n",t,j,f[i][j]*ipw[t][i]);
	}
	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]=(g[i]+((i-j)&1?mod-C[i][j]:C[i][j])*g[j])%mod;
	for(int i=1,c=m;i<=n;i++){
		ans=(ans+c*g[i])%mod;
		c=c*(m-i)%mod*power(i+1,mod-2)%mod;
	}
	printf("%lld\n",ans);
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 10032kb

input:

2 2 1000000007

output:

2

result:

ok 1 number(s): "2"

Test #2:

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

input:

3 4 1000000009

output:

36

result:

ok 1 number(s): "36"

Test #3:

score: 0
Accepted
time: 137ms
memory: 12836kb

input:

228 112263 998244353

output:

379700769

result:

ok 1 number(s): "379700769"

Test #4:

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

input:

1 1 998595277

output:

1

result:

ok 1 number(s): "1"

Test #5:

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

input:

2 2 998683811

output:

2

result:

ok 1 number(s): "2"

Test #6:

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

input:

3 1 998277223

output:

0

result:

ok 1 number(s): "0"

Test #7:

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

input:

4 1 998365733

output:

0

result:

ok 1 number(s): "0"

Test #8:

score: 0
Accepted
time: 741ms
memory: 13508kb

input:

400 100000000 998244353

output:

318973800

result:

ok 1 number(s): "318973800"

Test #9:

score: 0
Accepted
time: 742ms
memory: 13508kb

input:

400 1 1000000007

output:

0

result:

ok 1 number(s): "0"

Test #10:

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

input:

2 9 999603883

output:

72

result:

ok 1 number(s): "72"

Test #11:

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

input:

1 1 998784541

output:

1

result:

ok 1 number(s): "1"

Test #12:

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

input:

3 3 999209353

output:

12

result:

ok 1 number(s): "12"

Test #13:

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

input:

4 12 999787531

output:

16544

result:

ok 1 number(s): "16544"

Test #14:

score: 0
Accepted
time: 743ms
memory: 13608kb

input:

400 3 998785127

output:

505031599

result:

ok 1 number(s): "505031599"

Test #15:

score: 0
Accepted
time: 741ms
memory: 13636kb

input:

400 77 999400643

output:

877578741

result:

ok 1 number(s): "877578741"

Test #16:

score: 0
Accepted
time: 742ms
memory: 13456kb

input:

400 374 998458939

output:

202865317

result:

ok 1 number(s): "202865317"

Test #17:

score: 0
Accepted
time: 740ms
memory: 13644kb

input:

400 77435643 999245677

output:

833344996

result:

ok 1 number(s): "833344996"

Test #18:

score: 0
Accepted
time: 735ms
memory: 13500kb

input:

399 72119824 999010279

output:

188282648

result:

ok 1 number(s): "188282648"

Test #19:

score: 0
Accepted
time: 732ms
memory: 13020kb

input:

398 22521432 999827603

output:

986913334

result:

ok 1 number(s): "986913334"

Test #20:

score: 0
Accepted
time: 725ms
memory: 13508kb

input:

397 77955743 998803427

output:

32764673

result:

ok 1 number(s): "32764673"