QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#48035 | #1084. Beautiful Sequence Unraveling | feecle6418 | AC ✓ | 447ms | 7572kb | C++14 | 1.7kb | 2022-09-11 12:23:35 | 2022-09-11 12:23:38 |
Judging History
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"