QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#48035#1084. Beautiful Sequence Unravelingfeecle6418AC ✓447ms7572kbC++141.7kb2022-09-11 12:23:352022-09-11 12:23:38

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-09-11 12:23:38]
  • Judged
  • Verdict: AC
  • Time: 447ms
  • Memory: 7572kb
  • [2022-09-11 12:23:35]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
int f[405][405],g[405][405][3];
int n,m,mod,pw[405][405],pwinv[405][405],a[405],inv[405];
typedef unsigned long long ull;
typedef __uint128_t L;
struct FastMod {
    ull b, m;
    FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
    ull reduce(ull a) {
        ull q = (ull)((L(m) * a) >> 64);
        ull r = a - q * b; // can be proven that 0 <= r < 2*b
        return r >= b ? r - b : r;
    }
}F(2);
int Interpolate(int n) {
	int sum=0;
	for(int i=1; i<=n; i++) {
		int s=a[i];
		for(int j=1; j<i; j++)s=1ll*s*inv[i-j]%mod*(m-j+mod)%mod;
		for(int j=i+1; j<=n; j++)s=1ll*s*inv[j-i]%mod*(m-j+mod)%mod*(mod-1)%mod;
		sum=(sum+s)%mod;
	}
	return sum;
}
void del(int &x,int y){
	x-=y,(x<0&&(x+=mod));
}
int main() {
	scanf("%d%d%d",&n,&m,&mod),F=FastMod(mod),f[0][0]=mod-1,inv[1]=1;
	for(int i=2;i<=n+1;i++)inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
	for(int i=0;i<=n+1;i++){
		pw[i][0]=pwinv[i][0]=1;
		for(int j=1;j<=n;j++){
			pw[i][j]=1ll*i*pw[i][j-1]%mod;
			pwinv[i][j]=1ll*inv[i]*pwinv[i][j-1]%mod;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n+1;j++){
			f[i][j]=(pw[j][i]-pw[j-1][i]+mod)%mod;
			for(int k=1; k<=j; k++){
				del(f[i][j],F.reduce(1ll*g[k][j][0]*pw[j-k+1][i]));
				f[i][j]=F.reduce(f[i][j]+1ll*g[k][j][1]*pw[j-k][i]);
				if(k<j)del(f[i][j],F.reduce(1ll*g[k][j][2]*pw[j-k-1][i]));
			}
		}
		for(int j=1;j<=n+1;j++){
			for(int k=j;k<=n+1;k++) {
				g[j][k][0]=F.reduce(g[j][k][0]+1ll*f[i][j]*pwinv[k-j+1][i]);
				g[j][k][1]=F.reduce(g[j][k][1]+2ll*f[i][j]%mod*pwinv[k-j][i]);
				if(j<k)g[j][k][2]=F.reduce(g[j][k][2]+1ll*f[i][j]*pwinv[k-j-1][i]);
			}
		}
	}
	for(int i=1; i<=n+1; i++)a[i]=(a[i-1]+f[n][i])%mod;
	cout<<Interpolate(n+1);
}

详细

Test #1:

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

input:

2 2 1000000007

output:

2

result:

ok 1 number(s): "2"

Test #2:

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

input:

3 4 1000000009

output:

36

result:

ok 1 number(s): "36"

Test #3:

score: 0
Accepted
time: 83ms
memory: 6360kb

input:

228 112263 998244353

output:

379700769

result:

ok 1 number(s): "379700769"

Test #4:

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

input:

1 1 998595277

output:

1

result:

ok 1 number(s): "1"

Test #5:

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

input:

2 2 998683811

output:

2

result:

ok 1 number(s): "2"

Test #6:

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

input:

3 1 998277223

output:

0

result:

ok 1 number(s): "0"

Test #7:

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

input:

4 1 998365733

output:

0

result:

ok 1 number(s): "0"

Test #8:

score: 0
Accepted
time: 443ms
memory: 7484kb

input:

400 100000000 998244353

output:

318973800

result:

ok 1 number(s): "318973800"

Test #9:

score: 0
Accepted
time: 439ms
memory: 7448kb

input:

400 1 1000000007

output:

0

result:

ok 1 number(s): "0"

Test #10:

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

input:

2 9 999603883

output:

72

result:

ok 1 number(s): "72"

Test #11:

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

input:

1 1 998784541

output:

1

result:

ok 1 number(s): "1"

Test #12:

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

input:

3 3 999209353

output:

12

result:

ok 1 number(s): "12"

Test #13:

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

input:

4 12 999787531

output:

16544

result:

ok 1 number(s): "16544"

Test #14:

score: 0
Accepted
time: 445ms
memory: 7320kb

input:

400 3 998785127

output:

505031599

result:

ok 1 number(s): "505031599"

Test #15:

score: 0
Accepted
time: 441ms
memory: 7316kb

input:

400 77 999400643

output:

877578741

result:

ok 1 number(s): "877578741"

Test #16:

score: 0
Accepted
time: 438ms
memory: 7572kb

input:

400 374 998458939

output:

202865317

result:

ok 1 number(s): "202865317"

Test #17:

score: 0
Accepted
time: 442ms
memory: 7564kb

input:

400 77435643 999245677

output:

833344996

result:

ok 1 number(s): "833344996"

Test #18:

score: 0
Accepted
time: 447ms
memory: 7452kb

input:

399 72119824 999010279

output:

188282648

result:

ok 1 number(s): "188282648"

Test #19:

score: 0
Accepted
time: 433ms
memory: 7556kb

input:

398 22521432 999827603

output:

986913334

result:

ok 1 number(s): "986913334"

Test #20:

score: 0
Accepted
time: 434ms
memory: 7392kb

input:

397 77955743 998803427

output:

32764673

result:

ok 1 number(s): "32764673"