QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#382872#7974. 染色valeriu#35 3591ms8148kbC++203.2kb2024-04-08 19:55:082024-07-04 03:33:49

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 03:33:49]
  • 评测
  • 测评结果:35
  • 用时:3591ms
  • 内存:8148kb
  • [2024-04-08 19:55:08]
  • 提交

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
*/


Details

Tip: Click on the bar to expand more detailed information

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

output:


result: