QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #406630 | #1084. Beautiful Sequence Unraveling | Doqe | AC ✓ | 420ms | 6408kb | C++23 | 1.2kb | 2024-05-07 15:29:07 | 2024-05-07 15:29:08 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=510;
int F[N][N],n,k,P,G[N],pw[N][N],s[N][N];
long long qpow(long long a,long long b)
{
long long ans=1;
while(b)
{
if(b&1)ans=ans*a%P;
a=a*a%P;b>>=1;
}
return ans;
}
int main()
{
cin>>n>>k>>P;
for(int i=1;i<=n;++i)
{
pw[i][0]=1;
for(int j=1;j<=n;++j)
pw[i][j]=1ll*pw[i][j-1]*i%P;
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
// cerr<<i<<","<<j<<endl;
int z=qpow(j,i),z1=qpow(j,i);
// for(int t=1;t<i;++t)
// for(int l=1;l<=j;++l)
// z=(z-(1ll*pw[l][t]-pw[l-1][t]+P)*(F[i-t][j-l+1]-F[i-t][j-l]+P))%P;
for(int l=1;l<=j;++l)
z1=(1ll*z1-s[j-l+1][l]+s[j-l+1][l-1]+P)%P;
z=(z%P+P)%P;z1=(z1%P+P)%P;
// cerr<<z<<":"<<z1<<endl;
// assert(z==z1);
F[i][j]=(z1+P)%P;
}
for(int j=1;j<=n;++j)
for(int k=0;k<=n;++k)
s[j][k]=(1ll*s[j][k]+F[i][j]-F[i][j-1]+P)*k%P;
}
// for(int i=1;i<=n;++i)cerr<<F[n][i]<<" ";cerr<<endl;
for(int i=1;i<=n;++i)
{
int x=1;
for(int j=1;j<=i;++j)
x=1ll*x*(i-j+1)%P*qpow(j,P-2)%P,
G[i]=(G[i]+1ll*x*((i-j&1)?-1:1)*F[n][j])%P;
}
long long ans=0;
int x=1;
for(int i=1;i<=n;++i)
x=1ll*x*(k-i+1)%P*qpow(i,P-2)%P,
(ans+=1ll*x*G[i])%=P;
cout<<(ans%P+P)%P<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5644kb
input:
2 2 1000000007
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
3 4 1000000009
output:
36
result:
ok 1 number(s): "36"
Test #3:
score: 0
Accepted
time: 83ms
memory: 4952kb
input:
228 112263 998244353
output:
379700769
result:
ok 1 number(s): "379700769"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
1 1 998595277
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
2 2 998683811
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
3 1 998277223
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 1ms
memory: 5636kb
input:
4 1 998365733
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 418ms
memory: 6288kb
input:
400 100000000 998244353
output:
318973800
result:
ok 1 number(s): "318973800"
Test #9:
score: 0
Accepted
time: 419ms
memory: 6008kb
input:
400 1 1000000007
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
2 9 999603883
output:
72
result:
ok 1 number(s): "72"
Test #11:
score: 0
Accepted
time: 1ms
memory: 5540kb
input:
1 1 998784541
output:
1
result:
ok 1 number(s): "1"
Test #12:
score: 0
Accepted
time: 1ms
memory: 5688kb
input:
3 3 999209353
output:
12
result:
ok 1 number(s): "12"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
4 12 999787531
output:
16544
result:
ok 1 number(s): "16544"
Test #14:
score: 0
Accepted
time: 414ms
memory: 6408kb
input:
400 3 998785127
output:
505031599
result:
ok 1 number(s): "505031599"
Test #15:
score: 0
Accepted
time: 415ms
memory: 5852kb
input:
400 77 999400643
output:
877578741
result:
ok 1 number(s): "877578741"
Test #16:
score: 0
Accepted
time: 419ms
memory: 6328kb
input:
400 374 998458939
output:
202865317
result:
ok 1 number(s): "202865317"
Test #17:
score: 0
Accepted
time: 420ms
memory: 5980kb
input:
400 77435643 999245677
output:
833344996
result:
ok 1 number(s): "833344996"
Test #18:
score: 0
Accepted
time: 417ms
memory: 6032kb
input:
399 72119824 999010279
output:
188282648
result:
ok 1 number(s): "188282648"
Test #19:
score: 0
Accepted
time: 412ms
memory: 5964kb
input:
398 22521432 999827603
output:
986913334
result:
ok 1 number(s): "986913334"
Test #20:
score: 0
Accepted
time: 410ms
memory: 5940kb
input:
397 77955743 998803427
output:
32764673
result:
ok 1 number(s): "32764673"