|
|
//n ^ 3
#include<iostream>
using namespace std;
#define int long long
const int M = 998244353;
const int N = 1005;
int C[N][N];
int f[5][N];
int n, a, b, c, d;
void init(){
for(int i = 0;i < N;i ++){
C[i][0] = 1;
for(int j = 1;j <= i;j ++){
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % M;
}
}
}
signed main(){
cin.tie(0) -> ios::sync_with_stdio(0);
cin >> n >> a >> b >> c >> d;
init();
int ans = 0;
int limit = min(a, min(b, min(c, min(d, n / 4))));
for(int i = 0;i <= limit;i ++){
int rev = n - 4 * i;
int lim[5] = {0, a - i, b - i, c - i, d - i};
for(int j = 0;j <= 4;j ++){
for(int k = 0;k <= rev;k ++){
f[j][k] = 0;
}
}
f[0][0] = 1;
for(int k = 1;k <= 4;k ++){
for(int j = 0;j <= rev;j ++){
for(int x = 0;x <= min(j, lim[k]);x ++){
f[k][j] = (f[k][j] + f[k - 1][j - x] * C[j][x] % M) % M;
}
}
}
int way = C[n - 3 * i][i] * f[4][rev] % M;
if(i & 1) ans = (ans - way + M) % M;
else ans = (ans + way) % M;
}
cout << ans << '\n';
return 0;
}
//n ^ 2 log n
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long
const int MOD = 998244353;
const int MAXN = 4005;
const int G = 3;
const int Gi = 332748118;
ll n, num[4];
ll fact[MAXN], inv[MAXN];
int rev[MAXN << 2];
ll A[MAXN << 2], B[MAXN << 2], Poly[MAXN << 2];
ll qpow(ll a, ll b){
ll res = 1;
while(b){
if(b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
void NTT(ll A[], int len, int op){
for(int i = 0;i < len;i ++) if(i < rev[i]) swap(A[i], A[rev[i]]);
for(int mid = 1;mid < len;mid <<= 1){
ll Wn = qpow(op == 1 ? G : Gi, (MOD - 1) / (mid << 1));
for(int i = 0;i < len;i += (mid << 1)){
ll wk = 1;
for(int j = 0;j < mid;j ++, wk = wk * Wn % MOD){
ll x = A[i + j], y = wk * A[i + j + mid] % MOD;
A[i + j] = (x + y) % MOD;
A[i + j + mid] = (x - y + MOD) % MOD;
}
}
}
if(op == -1){
ll invL = qpow(len, MOD - 2);
for(int i = 0;i < len;i ++) A[i] = A[i] * invL % MOD;
}
}
void NTT_init(int len){
int L = 0; while((1 << L) < len) L ++;
for(int i = 0;i < len;i ++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (L - 1));
}
void init(){
fact[0] = 1;
for(int i = 1;i < MAXN;i ++) fact[i] = fact[i - 1] * i % MOD;
inv[MAXN - 1] = qpow(fact[MAXN - 1], MOD - 2);
for(int i = MAXN - 2;i >= 0;i --) inv[i] = inv[i + 1] * (i + 1) % MOD;
}
ll C(int n, int m){
if(m < 0 || m > n) return 0;
return fact[n] * inv[m] % MOD * inv[n - m] % MOD;
}
ll NFT(int k){
int m = n - 4 * k;
if(m < 0) return 0;
int len = 1;
while(len <= 4 * m) len <<= 1;
NTT_init(len);
for(int i = 0;i < len;i ++) Poly[i] = 1;
for(int i = 0;i < 4;i ++){
int limit = num[i] - k;
for(int j = 0;j < len;j ++) A[j] = (j <= limit && j <= m) ? inv[j] : 0;
NTT(A, len, 1);
for(int j = 0;j < len;j ++) Poly[j] = Poly[j] * A[j] % MOD;
}
NTT(Poly, len, -1);
return C(n - 3 * k, k) * Poly[m] % MOD * fact[m] % MOD;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
init();
cin >> n >> num[0] >> num[1] >> num[2] >> num[3];
ll ans = 0;
int lim_k = min({(ll)n / 4, num[0], num[1], num[2], num[3]});
for(int k = 0;k <= lim_k;k ++){
ll res = NFT(k);
if(k & 1) ans = (ans - res + MOD) % MOD;
else ans = (ans + res) % MOD;
}
cout << ans << '\n';
return 0;
}
题目4398 孤独摇滚!
1
评论
2026-05-04 16:45:04
|