QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#382972#7974. 染色valeriu#45 556ms8256kbC++203.5kb2024-04-08 20:35:592024-07-04 03:33:51

Judging History

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

  • [2024-07-04 03:33:51]
  • 评测
  • 测评结果:45
  • 用时:556ms
  • 内存:8256kb
  • [2024-04-08 20:35:59]
  • 提交

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, 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;
   }
};

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);
   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: 3ms
memory: 7668kb

input:

3 5 7

output:

105

result:

ok single line: '105'

Test #2:

score: 5
Accepted
time: 5ms
memory: 7916kb

input:

4 4 8

output:

144

result:

ok single line: '144'

Test #3:

score: 5
Accepted
time: 8ms
memory: 7884kb

input:

9 7 53

output:

11271960

result:

ok single line: '11271960'

Test #4:

score: 5
Accepted
time: 6ms
memory: 7672kb

input:

10 10 60

output:

711797984

result:

ok single line: '711797984'

Test #5:

score: 5
Accepted
time: 260ms
memory: 7824kb

input:

50 100 100

output:

684521374

result:

ok single line: '684521374'

Test #6:

score: 5
Accepted
time: 520ms
memory: 7888kb

input:

69 69 99

output:

205514286

result:

ok single line: '205514286'

Test #7:

score: 5
Accepted
time: 427ms
memory: 7984kb

input:

500 10 3232

output:

571588252

result:

ok single line: '571588252'

Test #8:

score: 5
Accepted
time: 556ms
memory: 7832kb

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: 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: 5
Accepted
time: 41ms
memory: 8256kb

input:

501 501 251001

output:

1

result:

ok single line: '1'