QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#685180 | #1084. Beautiful Sequence Unraveling | Rikku_eq | AC ✓ | 4020ms | 8980kb | C++14 | 2.6kb | 2024-10-28 18:07:59 | 2024-10-28 18:08:00 |
Judging History
answer
#include <bits/stdc++.h>
#define N 405
using namespace std;
typedef long long ll;
int n, K, mod;
ll pre[N], inv[N];
ll g[N][N][3], cur[3], f[N][N], tmp[N];
ll pw (ll bs, ll t)
{
ll res=1;
while (t) {
if (t&1) { res=res*bs%mod; }
bs=bs*bs%mod; t>>=1;
}
return res;
}
ll C (ll x, ll y)
{
ll res=1;
for (int i=0; i<y; i++) { res=res*(x-i)%mod; }
res=res*inv[y] %mod;
return res;
}
int main ()
{
// freopen("0test.in", "r", stdin);
// freopen("0test.out", "w", stdout);
scanf("%d %d %d", &n, &K, &mod);
for (int j=1; j<=n; j++) {
for (int w=1; w<j; w++) {
ll jw1=pw(j-w+1, mod-2), jw=pw(j-w, mod-2), jw_1=pw(j-w-1, mod-2);
cur[0]=cur[1]=cur[2]=1;
for (int k=1; k<=n; k++) {
(cur[0]*=jw1)%=mod;
(cur[1]*=jw)%=mod;
(cur[2]*=jw_1)%=mod;
for (int tg=0; tg<3; tg++) {
g[w][k][tg]=g[w][k-1][tg]+f[w][k]*cur[tg] %mod;
g[w][k][tg]%=mod;
}
}
}
for (int w=1; w<j; w++) {
cur[0]=cur[1]=cur[2]=1;
for (int i=1; i<=n; i++) {
(cur[0]*=(j-w+1))%=mod;
(cur[1]*=(j-w))%=mod;
(cur[2]*=(j-w-1))%=mod;
f[j][i]+=g[w][i-1][0]*cur[0] %mod + mod - 2ll*g[w][i-1][1]*cur[1] %mod + g[w][i-1][2]*cur[2] %mod;
f[j][i]%=mod;
}
}
ll pwj=1, pwj1=1, sum=0;
for (int i=1; i<=n; i++) {
pwj=pwj*j %mod; pwj1=pwj1*(mod-1+j) %mod;
f[j][i]=mod-f[j][i];
f[j][i]+=pwj+(mod-pwj1)+(mod-sum); f[j][i]%=mod;
sum=(sum+f[j][i])%mod;
if (i!=n) {
for (int k=j; k<=n; k++) {
tmp[k]+=mod- f[j][i]*(pw(k-j+1, n-i)+mod-pw(k-j, n-i)) %mod;
tmp[k]%=mod;
}
}
}
}
pre[0]=1; for (int i=1; i<=n; i++) { pre[i]=pre[i-1]*(ll)i %mod; }
inv[n]=pw(pre[n], mod-2);
for (int i=n-1; i>=0; i--) { inv[i]=inv[i+1]*(ll)(i+1) %mod; }
// for (int i=1; i<=n; i++) { cout<<tmp[i]<<" "; } cout<<endl;
for (int i=1; i<=n; i++) { tmp[i]+=pw(i, n); tmp[i]%=mod; }
for (int i=1; i<=n; i++) {
for (int j=1; j<i; j++) {
tmp[i]+=mod-tmp[j]*pre[i] %mod *inv[j] %mod *inv[i-j]%mod; tmp[i]%=mod;
}
}
ll ans=0;
for (int i=1; i<=n; i++) {
(tmp[i]*=C(K, i))%=mod; ans+=tmp[i]; ans%=mod;
}
printf("%lld\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3892kb
input:
2 2 1000000007
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
3 4 1000000009
output:
36
result:
ok 1 number(s): "36"
Test #3:
score: 0
Accepted
time: 709ms
memory: 7708kb
input:
228 112263 998244353
output:
379700769
result:
ok 1 number(s): "379700769"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
1 1 998595277
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
2 2 998683811
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3972kb
input:
3 1 998277223
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
4 1 998365733
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 4020ms
memory: 8888kb
input:
400 100000000 998244353
output:
318973800
result:
ok 1 number(s): "318973800"
Test #9:
score: 0
Accepted
time: 4005ms
memory: 8884kb
input:
400 1 1000000007
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
2 9 999603883
output:
72
result:
ok 1 number(s): "72"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
1 1 998784541
output:
1
result:
ok 1 number(s): "1"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
3 3 999209353
output:
12
result:
ok 1 number(s): "12"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3976kb
input:
4 12 999787531
output:
16544
result:
ok 1 number(s): "16544"
Test #14:
score: 0
Accepted
time: 4002ms
memory: 8892kb
input:
400 3 998785127
output:
505031599
result:
ok 1 number(s): "505031599"
Test #15:
score: 0
Accepted
time: 4013ms
memory: 8876kb
input:
400 77 999400643
output:
877578741
result:
ok 1 number(s): "877578741"
Test #16:
score: 0
Accepted
time: 4008ms
memory: 8952kb
input:
400 374 998458939
output:
202865317
result:
ok 1 number(s): "202865317"
Test #17:
score: 0
Accepted
time: 4013ms
memory: 8952kb
input:
400 77435643 999245677
output:
833344996
result:
ok 1 number(s): "833344996"
Test #18:
score: 0
Accepted
time: 3982ms
memory: 8888kb
input:
399 72119824 999010279
output:
188282648
result:
ok 1 number(s): "188282648"
Test #19:
score: 0
Accepted
time: 3954ms
memory: 8892kb
input:
398 22521432 999827603
output:
986913334
result:
ok 1 number(s): "986913334"
Test #20:
score: 0
Accepted
time: 3921ms
memory: 8980kb
input:
397 77955743 998803427
output:
32764673
result:
ok 1 number(s): "32764673"