QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#382872 | #7974. 染色 | valeriu# | 35 | 3591ms | 8148kb | C++20 | 3.2kb | 2024-04-08 19:55:08 | 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) { return Mint(val + x.val); }
Mint operator -(const Mint& x) { return Mint(val - x.val); }
Mint operator *(const Mint& x) { 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 {
vector<Mint> dp[nmax];
Mint& operator ()(int a, int b) {
if(sz(dp[a]) <= b) dp[a].resize(b + 1, Mint(0));
return dp[a][b];
}
Mint get(int a, int b) const {
if(sz(dp[a]) <= b) return Mint(0);
return dp[a][b];
}
void transition(const DP& from, int m, int limk) {
for(int i = 0; i <= m; i++)
dp[i].clear();
for(int zero = 0; zero <= m; zero++) {
for(int a = 0; a <= zero; a++) {
for(int b = 1 - (a % 2); b <= m - zero; b += 2) {
for(int kbef = 0; kbef <= limk; kbef++) {
//if(zero == m && a == m && b == 0 && kbef == 0) cerr << zero << ' ' << kbef << '\t' << zero - a + b << ' ' << kbef + a + b << '\t' << from.get(zero, kbef).val << ' ' << (COMBI::ncr(zero, a) * COMBI::ncr(m - zero, b)).val << '\n';;
(*this)(zero - a + b, kbef + a + b) += from.get(zero, kbef) * COMBI::ncr(zero, a) * COMBI::ncr(m - zero, b);
}
}
}
}
return;
}
};
signed main() {
COMBI::init();
cin.tie(0) -> sync_with_stdio(0);
int n, m, k;
cin >> n >> m >> k;
if(k % 2 != n % 2 || k % 2 != m % 2) {
cout << "0\n";
return 0;
}
if(n < m) swap(n, m);
DP start;
start(m, 0) = 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(0, k).val << '\n';
}
/**
Anul asta nu se da centroid
-- Rugaciunile mele
*/
詳細信息
Test #1:
score: 5
Accepted
time: 8ms
memory: 7788kb
input:
3 5 7
output:
105
result:
ok single line: '105'
Test #2:
score: 5
Accepted
time: 8ms
memory: 7660kb
input:
4 4 8
output:
144
result:
ok single line: '144'
Test #3:
score: 5
Accepted
time: 9ms
memory: 7804kb
input:
9 7 53
output:
11271960
result:
ok single line: '11271960'
Test #4:
score: 5
Accepted
time: 9ms
memory: 7656kb
input:
10 10 60
output:
711797984
result:
ok single line: '711797984'
Test #5:
score: 5
Accepted
time: 2076ms
memory: 7796kb
input:
50 100 100
output:
684521374
result:
ok single line: '684521374'
Test #6:
score: 5
Accepted
time: 3591ms
memory: 8148kb
input:
69 69 99
output:
205514286
result:
ok single line: '205514286'
Test #7:
score: 5
Accepted
time: 2598ms
memory: 7956kb
input:
500 10 3232
output:
571588252
result:
ok single line: '571588252'
Test #8:
score: 0
Time Limit Exceeded
input:
70 70 4800
output:
result:
Test #9:
score: 0
Time Limit Exceeded
input:
100 1000 50000
output:
result:
Test #10:
score: 0
Time Limit Exceeded
input:
316 316 4238
output:
result:
Test #11:
score: 0
Time Limit Exceeded
input:
201 479 30001
output:
result:
Test #12:
score: 0
Time Limit Exceeded
input:
706 706 706
output:
result:
Test #13:
score: 0
Time Limit Exceeded
input:
2023 233 2023
output:
result:
Test #14:
score: 0
Time Limit Exceeded
input:
402 402 1000
output:
result:
Test #15:
score: 0
Time Limit Exceeded
input:
707 333 999
output:
result:
Test #16:
score: 0
Time Limit Exceeded
input:
600 600 18000
output:
result:
Test #17:
score: 0
Time Limit Exceeded
input:
389 1047 40001
output:
result:
Test #18:
score: 0
Time Limit Exceeded
input:
707 707 42837
output:
result:
Test #19:
score: 0
Time Limit Exceeded
input:
100 5000 32346
output:
result:
Test #20:
score: 0
Time Limit Exceeded
input:
501 501 251001