QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#383013 | #7974. 染色 | valeriu# | 55 | 2344ms | 8192kb | C++20 | 4.2kb | 2024-04-08 20:55:06 | 2024-07-04 03:33:52 |
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 {
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, int flip) {
for(int i = 0; i <= m; i++)
dp[i].clear();
for(int zero = 0; zero <= m; zero++) {
for(int kbef = 0; kbef <= limk; kbef++) {
if(from.get(zero, kbef).val == 0) continue;
for(int a = 0; a <= zero; a++) {
for(int b = (flip ^ 1 ^ (a % 2)); b <= m - zero; b += 2) {
//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;
}
};
struct DPG {
Mint dp[nmax];
void transition(const DPG& 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 % 2 != n % 2 || k % 2 != m % 2) {
cout << "0\n";
return 0;
}
if(max(n, m) == k) {
if(n > m) swap(n, m);
DPG 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';
return 0;
}
if(n < m) swap(n, m);
int flip = 0;
if(n % 2 == 1 && k > n * m - k) {
flip = 1;
k = n * m - k;
}
else if(n % 2 == 0)
k = min(n * m - k, k);
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), flip);
//cerr << start(0, 3).val << '\n';
}
cout << (flip? start(m, k) : start(0, k)).val << '\n';
}
/**
Anul asta nu se da centroid
-- Rugaciunile mele
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 5
Accepted
time: 4ms
memory: 7976kb
input:
3 5 7
output:
105
result:
ok single line: '105'
Test #2:
score: 5
Accepted
time: 9ms
memory: 7688kb
input:
4 4 8
output:
144
result:
ok single line: '144'
Test #3:
score: 5
Accepted
time: 4ms
memory: 7720kb
input:
9 7 53
output:
11271960
result:
ok single line: '11271960'
Test #4:
score: 5
Accepted
time: 6ms
memory: 7916kb
input:
10 10 60
output:
711797984
result:
ok single line: '711797984'
Test #5:
score: 5
Accepted
time: 10ms
memory: 7704kb
input:
50 100 100
output:
684521374
result:
ok single line: '684521374'
Test #6:
score: 5
Accepted
time: 524ms
memory: 8088kb
input:
69 69 99
output:
205514286
result:
ok single line: '205514286'
Test #7:
score: 5
Accepted
time: 422ms
memory: 7960kb
input:
500 10 3232
output:
571588252
result:
ok single line: '571588252'
Test #8:
score: 5
Accepted
time: 569ms
memory: 7828kb
input:
70 70 4800
output:
851456413
result:
ok single line: '851456413'
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: 5
Accepted
time: 882ms
memory: 7912kb
input:
706 706 706
output:
835727049
result:
ok single line: '835727049'
Test #13:
score: 5
Accepted
time: 2344ms
memory: 7976kb
input:
2023 233 2023
output:
801992885
result:
ok single line: '801992885'
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: 5
Accepted
time: 37ms
memory: 8192kb
input:
501 501 251001
output:
1
result:
ok single line: '1'