QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#44295 | #1084. Beautiful Sequence Unraveling | xiaoyaowudi | AC ✓ | 236ms | 8972kb | C++14 | 2.1kb | 2022-08-15 09:27:15 | 2022-08-15 09:27:16 |
Judging History
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"