QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#382887 | #7974. 染色 | valeriu# | 15 | 2346ms | 7644kb | C++20 | 2.6kb | 2024-04-08 20:04:25 | 2024-07-04 03:33:49 |
Judging History
answer
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
//#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int mod = 998244353;
struct Mint {
int val;
Mint(ll x = 0): val((x % mod + mod) % mod) {;}
Mint operator +(const Mint& x) const { return Mint(val + x.val); }
Mint operator -(const Mint& x) const { return Mint(val - x.val); }
Mint operator *(const Mint& x) const { return Mint((ll)val * x.val); }
Mint operator +=(const Mint& x) { return *this = Mint(val + x.val); }
Mint operator -=(const Mint& x) { return *this = Mint(val - x.val); }
Mint operator *=(const Mint& x) { return *this = Mint((ll)val * x.val); }
Mint operator ^(const int& _b) const {
Mint accum = 1, a = *this;
int b = _b;
while(b) {
accum = (b & 1? accum * a : accum);
a *= a;
b >>= 1;
}
return accum;
}
Mint operator /(const Mint& x) { return Mint((ll)val * (x ^ (mod - 2)).val); }
Mint operator /=(const Mint& x) { return *this = Mint((ll)val * (x ^ (mod - 2)).val); }
};
namespace COMBI {
const int nmax = 5e5 + 5;
Mint fact[nmax], invfact[nmax];
void init(int n = nmax - 1) {
fact[0] = 1;
for(int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
invfact[n] = Mint(1) / fact[n];
for(int i = n; i > 0; i--) invfact[i - 1] = invfact[i] * Mint(i);
return;
}
Mint f(int n) { return fact[n]; }
Mint invf(int n) { return invfact[n]; }
Mint ncr(int n, int r) { return fact[n] * invfact[r] * invfact[n - r]; }
}
const int nmax = 5e3 + 5;
struct DP {
Mint dp[nmax];
void transition(const DP& from, int m, int limk) {
for(int i = 0; i <= m; i++)
dp[i] = 0;
for(int zero = 0; zero <= m; zero++) {
for(int a = 1; a <= zero; a += 2) {
dp[zero - a] += from.dp[zero] * COMBI::ncr(zero, a);
}
}
return;
}
};
signed main() {
COMBI::init();
cin.tie(0) -> sync_with_stdio(0);
int n, m, k;
cin >> n >> m >> k;
if(k < max(n, m)) {
cout << "0\n";
return 0;
}
if(k % 2 != n % 2 || k % 2 != m % 2) {
cout << "0\n";
return 0;
}
if(n > m) swap(n, m);
DP start;
start.dp[m] = 1;
for(int i = 1; i <= n; i++) {
auto lz = start;
start.transition(lz, m, min(i * (m - 1 + (m % 2)), k));
//cerr << start(0, 3).val << '\n';
}
cout << start.dp[0].val << '\n';
}
/**
Anul asta nu se da centroid
-- Rugaciunile mele
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 8ms
memory: 7616kb
input:
3 5 7
output:
60
result:
wrong answer 1st lines differ - expected: '105', found: '60'
Test #2:
score: 0
Wrong Answer
time: 4ms
memory: 7544kb
input:
4 4 8
output:
24
result:
wrong answer 1st lines differ - expected: '144', found: '24'
Test #3:
score: 0
Wrong Answer
time: 4ms
memory: 7640kb
input:
9 7 53
output:
423360
result:
wrong answer 1st lines differ - expected: '11271960', found: '423360'
Test #4:
score: 0
Wrong Answer
time: 8ms
memory: 7612kb
input:
10 10 60
output:
3628800
result:
wrong answer 1st lines differ - expected: '711797984', found: '3628800'
Test #5:
score: 5
Accepted
time: 10ms
memory: 7644kb
input:
50 100 100
output:
684521374
result:
ok single line: '684521374'
Test #6:
score: 0
Wrong Answer
time: 6ms
memory: 7512kb
input:
69 69 99
output:
932731521
result:
wrong answer 1st lines differ - expected: '205514286', found: '932731521'
Test #7:
score: 0
Wrong Answer
time: 11ms
memory: 7492kb
input:
500 10 3232
output:
586063172
result:
wrong answer 1st lines differ - expected: '571588252', found: '586063172'
Test #8:
score: 0
Wrong Answer
time: 9ms
memory: 7576kb
input:
70 70 4800
output:
405323525
result:
wrong answer 1st lines differ - expected: '851456413', found: '405323525'
Test #9:
score: 0
Wrong Answer
time: 254ms
memory: 7560kb
input:
100 1000 50000
output:
969717552
result:
wrong answer 1st lines differ - expected: '437541409', found: '969717552'
Test #10:
score: 0
Wrong Answer
time: 83ms
memory: 7640kb
input:
316 316 4238
output:
88751406
result:
wrong answer 1st lines differ - expected: '753478761', found: '88751406'
Test #11:
score: 0
Wrong Answer
time: 118ms
memory: 7548kb
input:
201 479 30001
output:
458293703
result:
wrong answer 1st lines differ - expected: '594408179', found: '458293703'
Test #12:
score: 5
Accepted
time: 872ms
memory: 7552kb
input:
706 706 706
output:
835727049
result:
ok single line: '835727049'
Test #13:
score: 5
Accepted
time: 2346ms
memory: 7576kb
input:
2023 233 2023
output:
801992885
result:
ok single line: '801992885'
Test #14:
score: 0
Wrong Answer
time: 164ms
memory: 7484kb
input:
402 402 1000
output:
223425145
result:
wrong answer 1st lines differ - expected: '940937548', found: '223425145'
Test #15:
score: 0
Wrong Answer
time: 414ms
memory: 7548kb
input:
707 333 999
output:
6904805
result:
wrong answer 1st lines differ - expected: '732112489', found: '6904805'
Test #16:
score: 0
Wrong Answer
time: 540ms
memory: 7556kb
input:
600 600 18000
output:
330648209
result:
wrong answer 1st lines differ - expected: '579276872', found: '330648209'
Test #17:
score: 0
Wrong Answer
time: 1055ms
memory: 7516kb
input:
389 1047 40001
output:
804581239
result:
wrong answer 1st lines differ - expected: '186903191', found: '804581239'
Test #18:
score: 0
Wrong Answer
time: 876ms
memory: 7552kb
input:
707 707 42837
output:
896611020
result:
wrong answer 1st lines differ - expected: '468460621', found: '896611020'
Test #19:
score: 0
Time Limit Exceeded
input:
100 5000 32346
output:
result:
Test #20:
score: 0
Wrong Answer
time: 314ms
memory: 7556kb
input:
501 501 251001
output:
729923376
result:
wrong answer 1st lines differ - expected: '1', found: '729923376'