QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#382887#7974. 染色valeriu#15 2346ms7644kbC++202.6kb2024-04-08 20:04:252024-07-04 03:33:49

Judging History

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

  • [2024-07-04 03:33:49]
  • 评测
  • 测评结果:15
  • 用时:2346ms
  • 内存:7644kb
  • [2024-04-08 20:04:25]
  • 提交

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'