QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#50175 | #4807. Melborp Lacissalc | sealnot123# | WA | 379ms | 54564kb | C++ | 1.5kb | 2022-09-25 02:15:53 | 2022-09-25 02:15:56 |
Judging History
answer
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define rep(i,a,b) for(int i=a; i<(b); ++i)
#define FOR(i,a,b) for(int i=a; i<=(b); ++i)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
const int mod = 998244353;
const int N = 66;
int dp[N][N][N*N];
int fac[N], cnr[N][N];
int mul(int a, int b) {
return a*1ll*b%mod;
}
int add(int a, int b) {
return (a+=b)>=mod? a-mod:a;
}
void adding(int &a, int b) {
a = add(a,b);
}
void solve() {
fac[0] = 1;
cnr[0][0] = 1;
FOR(i, 1, N-1) {
fac[i] = mul(fac[i-1],i);
cnr[i][0] = 1;
FOR(j, 1, i) {
cnr[i][j] = add(cnr[i-1][j-1], cnr[i-1][j]);
//printf("(%d,%d) = %d\n",i,j,cnr[i][j]);
}
}
int n, k, t;
scanf("%d %d %d",&n,&k,&t);
// initialize
FOR(j, 0, n) {
dp[0][j][j*(j+1)/2] = cnr[n][j];
}
// dp
FOR(i, 1, k-1) {
FOR(j, 0, n) {
FOR(l, 0, n) {
if(j+l > n) break;
FOR(m, 0, n*(n-1)/2) {
if(m+l*(l-1)/2 > n*(n-1)/2) break;
adding(dp[i][j+l][m+l*(l-1)/2], mul(dp[i-1][j][m], cnr[n-j][l]));
}
}
}
}
printf("%d",dp[k-1][n][t]);
}
int main() {
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 7920kb
input:
2 5 1
output:
12
result:
ok 1 number(s): "12"
Test #2:
score: 0
Accepted
time: 2ms
memory: 10060kb
input:
7 10 15
output:
2016
result:
ok 1 number(s): "2016"
Test #3:
score: 0
Accepted
time: 89ms
memory: 26560kb
input:
46 50 171
output:
645560469
result:
ok 1 number(s): "645560469"
Test #4:
score: 0
Accepted
time: 379ms
memory: 54492kb
input:
64 64 0
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 377ms
memory: 54564kb
input:
64 64 1
output:
326126263
result:
ok 1 number(s): "326126263"
Test #6:
score: 0
Accepted
time: 351ms
memory: 53408kb
input:
63 64 0
output:
4476118
result:
ok 1 number(s): "4476118"
Test #7:
score: 0
Accepted
time: 3ms
memory: 11868kb
input:
11 45 14
output:
963276342
result:
ok 1 number(s): "963276342"
Test #8:
score: 0
Accepted
time: 10ms
memory: 13156kb
input:
35 20 565
output:
0
result:
ok 1 number(s): "0"
Test #9:
score: 0
Accepted
time: 2ms
memory: 10872kb
input:
3 64 5
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 27ms
memory: 18848kb
input:
35 45 153
output:
181934997
result:
ok 1 number(s): "181934997"
Test #11:
score: 0
Accepted
time: 1ms
memory: 10228kb
input:
3 25 5
output:
0
result:
ok 1 number(s): "0"
Test #12:
score: 0
Accepted
time: 5ms
memory: 8224kb
input:
35 5 373
output:
740122840
result:
ok 1 number(s): "740122840"
Test #13:
score: 0
Accepted
time: 1ms
memory: 10620kb
input:
3 50 5
output:
0
result:
ok 1 number(s): "0"
Test #14:
score: 0
Accepted
time: 14ms
memory: 15536kb
input:
35 30 592
output:
0
result:
ok 1 number(s): "0"
Test #15:
score: 0
Accepted
time: 3ms
memory: 10092kb
input:
3 11 1
output:
540
result:
ok 1 number(s): "540"
Test #16:
score: 0
Accepted
time: 39ms
memory: 21116kb
input:
35 55 352
output:
656633208
result:
ok 1 number(s): "656633208"
Test #17:
score: 0
Accepted
time: 109ms
memory: 26820kb
input:
54 38 356
output:
215089708
result:
ok 1 number(s): "215089708"
Test #18:
score: 0
Accepted
time: 7ms
memory: 11376kb
input:
22 19 189
output:
0
result:
ok 1 number(s): "0"
Test #19:
score: 0
Accepted
time: 197ms
memory: 39936kb
input:
54 63 401
output:
987604839
result:
ok 1 number(s): "987604839"
Test #20:
score: 0
Accepted
time: 3ms
memory: 13940kb
input:
22 43 171
output:
827743481
result:
ok 1 number(s): "827743481"
Test #21:
score: 0
Accepted
time: 76ms
memory: 19400kb
input:
54 24 446
output:
551546514
result:
ok 1 number(s): "551546514"
Test #22:
score: 0
Accepted
time: 0ms
memory: 5972kb
input:
22 4 152
output:
0
result:
ok 1 number(s): "0"
Test #23:
score: 0
Accepted
time: 153ms
memory: 32064kb
input:
54 48 1306
output:
0
result:
ok 1 number(s): "0"
Test #24:
score: 0
Accepted
time: 0ms
memory: 12484kb
input:
22 29 7
output:
374430631
result:
ok 1 number(s): "374430631"
Test #25:
score: 0
Accepted
time: 16ms
memory: 11360kb
input:
54 9 1351
output:
0
result:
ok 1 number(s): "0"
Test #26:
score: 0
Accepted
time: 6ms
memory: 15280kb
input:
22 54 5
output:
267958047
result:
ok 1 number(s): "267958047"
Test #27:
score: 0
Accepted
time: 187ms
memory: 29832kb
input:
64 32 1315
output:
494251101
result:
ok 1 number(s): "494251101"
Test #28:
score: 0
Accepted
time: 9ms
memory: 11196kb
input:
33 12 332
output:
765350074
result:
ok 1 number(s): "765350074"
Test #29:
score: -100
Wrong Answer
time: 0ms
memory: 10396kb
input:
1 57 1
output:
0
result:
wrong answer 1st numbers differ - expected: '1', found: '0'