Submission #5898858
Source Code Expand
#include <iostream> #define llint long long #define mod 998244353 using namespace std; llint n, x; llint dp[3005][6005]; llint cnt[3005]; const int FACT_MAX = 3005; llint fact[FACT_MAX], fact_inv[FACT_MAX]; llint modpow(llint a, llint n) { if(n == 0) return 1; if(n % 2){ return ((a%mod) * (modpow(a, n-1)%mod)) % mod; } else{ return modpow((a*a)%mod, n/2) % mod; } } void make_fact() { llint val = 1; fact[0] = 1; for(int i = 1; i < FACT_MAX; i++){ val *= i; val %= mod; fact[i] = val; } fact_inv[FACT_MAX-1] = modpow(fact[FACT_MAX-1], mod-2); for(int i = FACT_MAX-2; i >= 0; i--){ fact_inv[i] = fact_inv[i+1] * (i+1) % mod; } } llint comb(llint n, llint k) { llint ret = 1; ret *= fact[n]; ret *= fact_inv[k], ret %= mod; ret *= fact_inv[n-k], ret %= mod; return ret; } int main(void) { cin >> n >> x; make_fact(); dp[0][0] = 1; for(int i = 0; i < n; i++){ for(int j = 0; j <= 2*n; j++){ for(int k = 1; k <= 2; k++){ if(j+k <= 2*n){ dp[i+1][j+k] += dp[i][j]; dp[i+1][j+k] %= mod; } } } } for(int i = 0; i <= n; i++){ for(int j = 0; j < x; j++){ cnt[i] += dp[i][j], cnt[i] %= mod; } } for(int i = 1; i <= n; i++){ for(int j = 0; j < i; j++){ if(2*j-i <= 0) continue; if((x-1)-2*(i-j) <= 0) continue; if((x-1)-2*(i-j) >= 2*(2*j-i)) continue; cnt[i] += dp[2*j-i][(x-1)-2*(i-j)]; cnt[i] %= mod; } if(x % 2 && 2*i > x) cnt[i]++, cnt[i] %= mod; } llint ans = 0; for(int i = 0; i <= n; i++){ ans += cnt[i] * comb(n, i) % mod; ans %= mod; } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Banned X |
User | leaf1415 |
Language | C++14 (GCC 5.4.1) |
Score | 800 |
Code Size | 1674 Byte |
Status | AC |
Exec Time | 167 ms |
Memory | 141184 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 800 / 800 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | s1.txt, s2.txt, s3.txt, s4.txt, s5.txt |
All | 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, s1.txt, s2.txt, s3.txt, s4.txt, s5.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01.txt | AC | 167 ms | 141056 KB |
02.txt | AC | 166 ms | 141184 KB |
03.txt | AC | 95 ms | 106368 KB |
04.txt | AC | 119 ms | 125056 KB |
05.txt | AC | 128 ms | 133248 KB |
06.txt | AC | 129 ms | 133248 KB |
07.txt | AC | 111 ms | 127104 KB |
08.txt | AC | 154 ms | 137472 KB |
09.txt | AC | 103 ms | 140544 KB |
10.txt | AC | 82 ms | 106368 KB |
11.txt | AC | 1 ms | 256 KB |
12.txt | AC | 1 ms | 256 KB |
13.txt | AC | 1 ms | 256 KB |
14.txt | AC | 1 ms | 256 KB |
15.txt | AC | 1 ms | 384 KB |
16.txt | AC | 100 ms | 141056 KB |
17.txt | AC | 163 ms | 140032 KB |
18.txt | AC | 156 ms | 137344 KB |
19.txt | AC | 101 ms | 141056 KB |
20.txt | AC | 16 ms | 41984 KB |
s1.txt | AC | 1 ms | 256 KB |
s2.txt | AC | 1 ms | 384 KB |
s3.txt | AC | 1 ms | 384 KB |
s4.txt | AC | 1 ms | 384 KB |
s5.txt | AC | 5 ms | 14976 KB |