QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#54500 | #1084. Beautiful Sequence Unraveling | tricyzhkx | AC ✓ | 238ms | 6944kb | C++14 | 1.5kb | 2022-10-09 08:15:28 | 2022-10-09 08:15:31 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;
struct Fastmod
{
int m;ll b;
void init(int _m){m=_m;b=((lll)1<<64)/m;}
int operator()(ll a)
{
ll q=((lll)a*b)>>64;a-=q*m;
return a>=m?a-m:a;
}
}Mod;
int mod,C[410][410],pw[410][410],ipw[410][410],f[410][410],g[410],sum[410][410];
int add(int a,int b){return (a+=b)>=mod?a-mod:a;}
int mul(int a,int b){return Mod((ll)a*b);}
int power(int a,int b)
{
int ans=1;
for(;b;b>>=1,a=mul(a,a))
if(b&1) ans=mul(ans,a);
return ans;
}
int main()
{
int n,K,ans=0;
cin>>n>>K>>mod;Mod.init(mod);
for(int i=1;i<=n;i++)
{
pw[0][i]=ipw[0][i]=1;
int iv=power(i,mod-2);
for(int j=1;j<=n;j++)
pw[j][i]=mul(pw[j-1][i],i),
ipw[j][i]=mul(ipw[j-1][i],iv);
}
for(int i=0;i<=n;i++) C[i][0]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
C[i][j]=add(C[i-1][j-1],C[i-1][j]);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
f[i][j]=pw[i][j];
for(int l=1;l<=j;l++)
f[i][j]=Mod(f[i][j]+(ll)(mod-pw[i][l])*sum[l][j-l+1]+
(ll)pw[i][l-1]*sum[l-1][j-l+1]+(ll)pw[i][l]*sum[l][j-l]+
(ll)(mod-pw[i][l-1])*sum[l-1][j-l]);
}
for(int l=1;l<=n;l++)
for(int j=1;j<=n;j++)
sum[l][j]=Mod(sum[l][j]+(ll)f[i][j]*ipw[i][l]);
}
for(int i=1;i<=n;i++) g[i]=f[n][i];
for(int i=n;i>=1;i--)
for(int j=1;j<i;j++)
g[i]=Mod(g[i]+(ll)((i-j)&1?mod-C[i][j]:C[i][j])*g[j]);
for(int i=1,c=K;i<=n;i++)
{
ans=Mod(ans+(ll)c*g[i]);
c=mul(mul(c,K-i),power(i+1,mod-2));
}
cout<<ans<<endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 5576kb
input:
2 2 1000000007
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 2ms
memory: 5688kb
input:
3 4 1000000009
output:
36
result:
ok 1 number(s): "36"
Test #3:
score: 0
Accepted
time: 45ms
memory: 6376kb
input:
228 112263 998244353
output:
379700769
result:
ok 1 number(s): "379700769"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
1 1 998595277
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 5692kb
input:
2 2 998683811
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
3 1 998277223
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 2ms
memory: 3652kb
input:
4 1 998365733
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 234ms
memory: 6920kb
input:
400 100000000 998244353
output:
318973800
result:
ok 1 number(s): "318973800"
Test #9:
score: 0
Accepted
time: 237ms
memory: 6692kb
input:
400 1 1000000007
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 3ms
memory: 5668kb
input:
2 9 999603883
output:
72
result:
ok 1 number(s): "72"
Test #11:
score: 0
Accepted
time: 2ms
memory: 5684kb
input:
1 1 998784541
output:
1
result:
ok 1 number(s): "1"
Test #12:
score: 0
Accepted
time: 3ms
memory: 5680kb
input:
3 3 999209353
output:
12
result:
ok 1 number(s): "12"
Test #13:
score: 0
Accepted
time: 2ms
memory: 3660kb
input:
4 12 999787531
output:
16544
result:
ok 1 number(s): "16544"
Test #14:
score: 0
Accepted
time: 228ms
memory: 6768kb
input:
400 3 998785127
output:
505031599
result:
ok 1 number(s): "505031599"
Test #15:
score: 0
Accepted
time: 229ms
memory: 6880kb
input:
400 77 999400643
output:
877578741
result:
ok 1 number(s): "877578741"
Test #16:
score: 0
Accepted
time: 238ms
memory: 6708kb
input:
400 374 998458939
output:
202865317
result:
ok 1 number(s): "202865317"
Test #17:
score: 0
Accepted
time: 230ms
memory: 6888kb
input:
400 77435643 999245677
output:
833344996
result:
ok 1 number(s): "833344996"
Test #18:
score: 0
Accepted
time: 234ms
memory: 6896kb
input:
399 72119824 999010279
output:
188282648
result:
ok 1 number(s): "188282648"
Test #19:
score: 0
Accepted
time: 224ms
memory: 6944kb
input:
398 22521432 999827603
output:
986913334
result:
ok 1 number(s): "986913334"
Test #20:
score: 0
Accepted
time: 231ms
memory: 6816kb
input:
397 77955743 998803427
output:
32764673
result:
ok 1 number(s): "32764673"