QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#55376 | #4807. Melborp Lacissalc | GZU_addd | WA | 163ms | 26128kb | C++ | 2.2kb | 2022-10-13 14:14:20 | 2022-10-13 14:14:24 |
Judging History
answer
#include<bits/stdc++.h>
#define ls u<<1
#define rs u<<1|1
#define fi first
#define se second
#define min amin
#define max amax
#define pb push_back
#define pq priority_queue
#define vt vector
#define lb(x) (x&-x)
#define sub(i,j) ((1LL*i-1LL*j)%k+k)%k
std::mt19937 rnd(233);
using namespace std;
using ll=long long;
//using node=pair<int,int>;
//using nnode=array<int,3>;
//inline int read(){
// int x=0,f=1;
// char c=getchar();
// while(c<'0'||c>'9'){
// if(c=='-') f=-1;
// c=getchar();
// }
// while(c>='0'&&c<='9'){
// x=x*10+(c^'0');
// c=getchar();
// }
// return x*f;
//}
template<typename T=int>T read(){T x;cin>>x;return x;}
template<typename U,typename V>auto min(U x,V y){return x<y?x:y;}
template<typename U,typename V>auto max(U x,V y){return x>y?x:y;}
template<typename U,typename...V>auto min(U x,V...y){return min(x,min(y...));}
template<typename U,typename...V>auto max(U x,V...y){return max(x,max(y...));}
template<typename U,typename V>bool cmin(U &x,V y){return x>y?x=y,true:false;}
template<typename U,typename V>bool cmax(U &x,V y){return x<y?x=y,true:false;}
constexpr int mod=998244353;
ll qpow(int x,int n=mod-2){ll y=1;for(;n;n>>=1,x=1LL*x*x%mod)if(n&1)y=1LL*y*x%mod;return y;}
//inline ll qpow(ll a, ll n=mod-2) { ll ans = 1; while (n) { if (n & 1) { ans *= a; }a *= a; n >>= 1; }return ans; }
constexpr int N=65,M=N*(N+1)/2;
constexpr ll inf=1e18;
int n,m,k,fac[N],infac[N],f[N][N][M];
int C(int x,int y){if(x<y)return 0;return 1LL*fac[x]*infac[y]%mod*infac[x-y]%mod;}
void solve(){
cin>>n>>k>>m;
f[0][0][0]=fac[0]=1;
for(int i=1;i<=n;++i)fac[i]=1LL*fac[i-1]*i%mod;
infac[n]=qpow(fac[n]);
for(int i=n-1;~i;--i)infac[i]=1LL*infac[i+1]*(i+1)%mod;
for(int i=1;i<=k;++i){
for(int j=1;j<=n;++j){
for(int l=1;l<=j;++l){
int del;
if(i==1)del=C(l+1,2);
else del=C(l,2);
for(int p=del;p<=m;++p)
f[i][j][p]=(f[i][j][p]+1LL*f[i-1][j-l][p-del]*C(j,l)%mod)%mod;
}
}
for(int j=0;j<=n;++j)for(int p=0;p<=m;++p)
f[i][j][p]=(f[i][j][p]+f[i-1][j][p])%mod;
}
cout<<max(0,f[k][n][m]-!m);
}
int main(){
cin.sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
// for(int T=read();T--;solve());
solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 5644kb
input:
2 5 1
output:
12
result:
ok 1 number(s): "12"
Test #2:
score: 0
Accepted
time: 3ms
memory: 5856kb
input:
7 10 15
output:
2016
result:
ok 1 number(s): "2016"
Test #3:
score: 0
Accepted
time: 15ms
memory: 15836kb
input:
46 50 171
output:
645560469
result:
ok 1 number(s): "645560469"
Test #4:
score: 0
Accepted
time: 7ms
memory: 21320kb
input:
64 64 0
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 2ms
memory: 21396kb
input:
64 64 1
output:
326126263
result:
ok 1 number(s): "326126263"
Test #6:
score: 0
Accepted
time: 7ms
memory: 21076kb
input:
63 64 0
output:
4476118
result:
ok 1 number(s): "4476118"
Test #7:
score: 0
Accepted
time: 5ms
memory: 7652kb
input:
11 45 14
output:
963276342
result:
ok 1 number(s): "963276342"
Test #8:
score: 0
Accepted
time: 18ms
memory: 9308kb
input:
35 20 565
output:
0
result:
ok 1 number(s): "0"
Test #9:
score: 0
Accepted
time: 3ms
memory: 6688kb
input:
3 64 5
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 13ms
memory: 12484kb
input:
35 45 153
output:
181934997
result:
ok 1 number(s): "181934997"
Test #11:
score: 0
Accepted
time: 0ms
memory: 6000kb
input:
3 25 5
output:
0
result:
ok 1 number(s): "0"
Test #12:
score: 0
Accepted
time: 5ms
memory: 6156kb
input:
35 5 373
output:
740122840
result:
ok 1 number(s): "740122840"
Test #13:
score: 0
Accepted
time: 3ms
memory: 6480kb
input:
3 50 5
output:
0
result:
ok 1 number(s): "0"
Test #14:
score: 0
Accepted
time: 22ms
memory: 11632kb
input:
35 30 592
output:
0
result:
ok 1 number(s): "0"
Test #15:
score: 0
Accepted
time: 2ms
memory: 5768kb
input:
3 11 1
output:
540
result:
ok 1 number(s): "540"
Test #16:
score: 0
Accepted
time: 29ms
memory: 15792kb
input:
35 55 352
output:
656633208
result:
ok 1 number(s): "656633208"
Test #17:
score: 0
Accepted
time: 30ms
memory: 15872kb
input:
54 38 356
output:
215089708
result:
ok 1 number(s): "215089708"
Test #18:
score: 0
Accepted
time: 2ms
memory: 7360kb
input:
22 19 189
output:
0
result:
ok 1 number(s): "0"
Test #19:
score: 0
Accepted
time: 58ms
memory: 23724kb
input:
54 63 401
output:
987604839
result:
ok 1 number(s): "987604839"
Test #20:
score: 0
Accepted
time: 5ms
memory: 10196kb
input:
22 43 171
output:
827743481
result:
ok 1 number(s): "827743481"
Test #21:
score: 0
Accepted
time: 15ms
memory: 12188kb
input:
54 24 446
output:
551546514
result:
ok 1 number(s): "551546514"
Test #22:
score: 0
Accepted
time: 3ms
memory: 5768kb
input:
22 4 152
output:
0
result:
ok 1 number(s): "0"
Test #23:
score: 0
Accepted
time: 163ms
memory: 26128kb
input:
54 48 1306
output:
0
result:
ok 1 number(s): "0"
Test #24:
score: 0
Accepted
time: 2ms
memory: 8168kb
input:
22 29 7
output:
374430631
result:
ok 1 number(s): "374430631"
Test #25:
score: 0
Accepted
time: 34ms
memory: 8048kb
input:
54 9 1351
output:
0
result:
ok 1 number(s): "0"
Test #26:
score: 0
Accepted
time: 2ms
memory: 10260kb
input:
22 54 5
output:
267958047
result:
ok 1 number(s): "267958047"
Test #27:
score: 0
Accepted
time: 133ms
memory: 20996kb
input:
64 32 1315
output:
494251101
result:
ok 1 number(s): "494251101"
Test #28:
score: 0
Accepted
time: 8ms
memory: 7208kb
input:
33 12 332
output:
765350074
result:
ok 1 number(s): "765350074"
Test #29:
score: -100
Wrong Answer
time: 0ms
memory: 5940kb
input:
1 57 1
output:
0
result:
wrong answer 1st numbers differ - expected: '1', found: '0'