QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#44295#1084. Beautiful Sequence UnravelingxiaoyaowudiAC ✓236ms8972kbC++142.1kb2022-08-15 09:27:152022-08-15 09:27:16

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-08-15 09:27:16]
  • Judged
  • Verdict: AC
  • Time: 236ms
  • Memory: 8972kb
  • [2022-08-15 09:27:15]
  • Submitted

answer

#include <iostream>
#include <algorithm>
#include <cstring>
constexpr int N=410;
typedef unsigned long long ull;
typedef __uint128_t L;
struct fm{
	ull b,m;
	fm()=default;
	fm(int p):b(p),m((L(1)<<64)/p){}
	ull W(ull k){
		ull q=((L(m)*k)>>64);
		ull r=k-q*b;
		return r>=b?r-b:r;
	}
}F;
int ff[2][N][N][2],gg[2][N][N][2],p,n,K,pv[N];
int W(int k){return k>=p?k-p:k;}
void W(int &a,int k){a+=k;if(a>=p) a-=p;}
int fp(int a,int b){int ans=1,off=a;while(b){if(b&1) ans=F.W(1ull*ans*off);off=F.W(1ull*off*off);b>>=1;}return ans;}
int main(){
	std::cin>>n>>K>>p;F=fm(p);
	ff[0][0][0][1]=1;
	for(int i=0;i<=n+1;++i) gg[0][i][0][1]=1;
	for(int i=1;i<=n;++i){
		std::memset(ff[i&1],0,sizeof(ff[i&1]));
		std::memset(gg[i&1],0,sizeof(gg[i&1]));
		int (&f1)[N][N][2]=ff[i&1],  (&g1)[N][N][2]=gg[i&1];
		int (&f0)[N][N][2]=ff[i&1^1],(&g0)[N][N][2]=gg[i&1^1];
		for(int j=1;j<=n+1;++j){
			unsigned long long cur=0;
			for(int k=0;k<=j;++k){
				unsigned long long u0=0,u1=0;
				{
					if(k!=j){
						u0+=g0[j][k][0];
						u1+=g0[j][k][1];
					}else{
						u1+=f0[j][k][0]+f0[j][k][1];
					}
				}
				if(k<j){
					{
						if(k) u1+=f0[j][k][0]+f0[j][k][1];
					}
					{
						u0+=1ull*f0[j][k][0]*(j-k-1);
						u1+=1ull*f0[j][k][1]*(j-k-1);
					}
				}
				f1[j][k][0]=F.W(u0);f1[j][k][1]=F.W(u1);
				cur+=f1[j][k][1];
			}
			W(f1[j][j][0],p-F.W(cur));
			// for(int k=0;k<=j;++k){
			// 	printf("%d %d %d %d %d\n",i,j,k,f[i][j][k][0],f[i][j][k][1]);
			// 	// g1[i][j][k][0]=W(g1[i][j-1][k][0]+f[i][j][k][0]);
			// 	// g1[i][j][k][1]=W(g1[i][j-1][k][1]+f[i][j][k][1]);
			// }
		}
		for(int j=1;j<=n+1;++j){
			for(int k=0;k<=n+1;++k){
				g1[j][k][0]=W(g1[j-1][k][0]+f1[j][k][0]);
				g1[j][k][1]=W(g1[j-1][k][1]+f1[j][k][1]);
			}
		}
	}
	for(int j=1,t=0;j<=n+1;++j){
		for(int k=0;k<=j;++k) W(t,ff[n&1][j][k][1]);
		pv[j]=t;
		// printf("%d %d\n",j,pv[j]);
	}
	int ans=0;
	for(int j=1;j<=n+1;++j){
		int coef=pv[j];
		for(int t=1;t<=n+1;++t) if(t!=j){
			coef=F.W(F.W(1ull*fp(p+j-t,p-2)*(p+K-t))*coef);
		}
		W(ans,coef);
	}
	std::cout<<ans<<std::endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 8736kb

input:

2 2 1000000007

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 6ms
memory: 8844kb

input:

3 4 1000000009

output:

36

result:

ok 1 number(s): "36"

Test #3:

score: 0
Accepted
time: 66ms
memory: 8744kb

input:

228 112263 998244353

output:

379700769

result:

ok 1 number(s): "379700769"

Test #4:

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

input:

1 1 998595277

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 5ms
memory: 8972kb

input:

2 2 998683811

output:

2

result:

ok 1 number(s): "2"

Test #6:

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

input:

3 1 998277223

output:

0

result:

ok 1 number(s): "0"

Test #7:

score: 0
Accepted
time: 5ms
memory: 8876kb

input:

4 1 998365733

output:

0

result:

ok 1 number(s): "0"

Test #8:

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

input:

400 100000000 998244353

output:

318973800

result:

ok 1 number(s): "318973800"

Test #9:

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

input:

400 1 1000000007

output:

0

result:

ok 1 number(s): "0"

Test #10:

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

input:

2 9 999603883

output:

72

result:

ok 1 number(s): "72"

Test #11:

score: 0
Accepted
time: 4ms
memory: 6184kb

input:

1 1 998784541

output:

1

result:

ok 1 number(s): "1"

Test #12:

score: 0
Accepted
time: 5ms
memory: 8744kb

input:

3 3 999209353

output:

12

result:

ok 1 number(s): "12"

Test #13:

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

input:

4 12 999787531

output:

16544

result:

ok 1 number(s): "16544"

Test #14:

score: 0
Accepted
time: 233ms
memory: 8960kb

input:

400 3 998785127

output:

505031599

result:

ok 1 number(s): "505031599"

Test #15:

score: 0
Accepted
time: 236ms
memory: 8960kb

input:

400 77 999400643

output:

877578741

result:

ok 1 number(s): "877578741"

Test #16:

score: 0
Accepted
time: 232ms
memory: 8916kb

input:

400 374 998458939

output:

202865317

result:

ok 1 number(s): "202865317"

Test #17:

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

input:

400 77435643 999245677

output:

833344996

result:

ok 1 number(s): "833344996"

Test #18:

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

input:

399 72119824 999010279

output:

188282648

result:

ok 1 number(s): "188282648"

Test #19:

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

input:

398 22521432 999827603

output:

986913334

result:

ok 1 number(s): "986913334"

Test #20:

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

input:

397 77955743 998803427

output:

32764673

result:

ok 1 number(s): "32764673"