QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#889503 | #1084. Beautiful Sequence Unraveling | Kangliyang | AC ✓ | 743ms | 13644kb | C++14 | 2.1kb | 2025-02-08 16:18:54 | 2025-02-08 16:18:58 |
Judging History
answer
#include <bits/stdc++.h>
#define in(x) freopen(#x".in","r",stdin)
#define out(x) freopen(#x".out","w",stdout)
#define make(x) freopen(#x".in","w",stdout)
#define ll long long
#define int long long
#ifdef MY_COMPUTER
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
#define vector basic_string
#define pii array<int,2>
using namespace std;
inline int read()
{
int s=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=s*10+ch-'0';
ch=getchar();
}
return s*f;
}
template<typename _it>
void read(_it a,_it b){
while(a!=b) (*a)=read(),a++;
}
template<typename _it>
void write(const char* form,_it a,_it b,int op=0){
while(a!=b) printf(form,*a),a++;
if(op) puts("");
}
int n,m,mod,f[510][510],sum[510][510],pw[510][510],ipw[510][510],C[510][510],ans,g[510];
//sum[t][j]:\sum f[i][j]/t^i
int power(int a,int b){
int ans=1;
while(b){
if(b&1) ans=ans*a%mod;
a=a*a%mod,b>>=1;
}
return ans;
}
signed main()
{
//ios::sync_with_stdio(false);
n=read(),m=read(),mod=read();
C[0][0]=1;
for(int i=1,ii;i<=n;i++){
ii=power(i,mod-2),C[i][0]=1;
pw[i][0]=ipw[i][0]=1;
for(int j=1;j<=n;j++){
pw[i][j]=pw[i][j-1]*i%mod;
ipw[i][j]=ipw[i][j-1]*ii%mod;
}
for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f[i][j]=pw[j][i];
for(int t=1;t<=j;t++){
f[i][j]-=pw[t][i]*sum[t][j-t+1]%mod;
f[i][j]+=pw[t][i]*sum[t][j-t]%mod;
f[i][j]+=pw[t-1][i]*sum[t-1][j-t+1]%mod;
f[i][j]-=pw[t-1][i]*sum[t-1][j-t]%mod;
f[i][j]=(f[i][j]%mod+mod)%mod;
}
}
for(int j=1;j<=n;j++)
for(int t=1;t<=n;t++)
sum[t][j]=(sum[t][j]+f[i][j]*ipw[t][i])%mod;//,printf("%lld %lld add %lld\n",t,j,f[i][j]*ipw[t][i]);
}
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]=(g[i]+((i-j)&1?mod-C[i][j]:C[i][j])*g[j])%mod;
for(int i=1,c=m;i<=n;i++){
ans=(ans+c*g[i])%mod;
c=c*(m-i)%mod*power(i+1,mod-2)%mod;
}
printf("%lld\n",ans);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 10032kb
input:
2 2 1000000007
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 1ms
memory: 9948kb
input:
3 4 1000000009
output:
36
result:
ok 1 number(s): "36"
Test #3:
score: 0
Accepted
time: 137ms
memory: 12836kb
input:
228 112263 998244353
output:
379700769
result:
ok 1 number(s): "379700769"
Test #4:
score: 0
Accepted
time: 0ms
memory: 10068kb
input:
1 1 998595277
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 10076kb
input:
2 2 998683811
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 0ms
memory: 10076kb
input:
3 1 998277223
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 0ms
memory: 8016kb
input:
4 1 998365733
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 741ms
memory: 13508kb
input:
400 100000000 998244353
output:
318973800
result:
ok 1 number(s): "318973800"
Test #9:
score: 0
Accepted
time: 742ms
memory: 13508kb
input:
400 1 1000000007
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 0ms
memory: 10072kb
input:
2 9 999603883
output:
72
result:
ok 1 number(s): "72"
Test #11:
score: 0
Accepted
time: 0ms
memory: 10068kb
input:
1 1 998784541
output:
1
result:
ok 1 number(s): "1"
Test #12:
score: 0
Accepted
time: 0ms
memory: 10040kb
input:
3 3 999209353
output:
12
result:
ok 1 number(s): "12"
Test #13:
score: 0
Accepted
time: 0ms
memory: 9952kb
input:
4 12 999787531
output:
16544
result:
ok 1 number(s): "16544"
Test #14:
score: 0
Accepted
time: 743ms
memory: 13608kb
input:
400 3 998785127
output:
505031599
result:
ok 1 number(s): "505031599"
Test #15:
score: 0
Accepted
time: 741ms
memory: 13636kb
input:
400 77 999400643
output:
877578741
result:
ok 1 number(s): "877578741"
Test #16:
score: 0
Accepted
time: 742ms
memory: 13456kb
input:
400 374 998458939
output:
202865317
result:
ok 1 number(s): "202865317"
Test #17:
score: 0
Accepted
time: 740ms
memory: 13644kb
input:
400 77435643 999245677
output:
833344996
result:
ok 1 number(s): "833344996"
Test #18:
score: 0
Accepted
time: 735ms
memory: 13500kb
input:
399 72119824 999010279
output:
188282648
result:
ok 1 number(s): "188282648"
Test #19:
score: 0
Accepted
time: 732ms
memory: 13020kb
input:
398 22521432 999827603
output:
986913334
result:
ok 1 number(s): "986913334"
Test #20:
score: 0
Accepted
time: 725ms
memory: 13508kb
input:
397 77955743 998803427
output:
32764673
result:
ok 1 number(s): "32764673"