Gravatar
终焉折枝
积分:1860
提交:230 / 406

Pro4398  孤独摇滚!

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

2026-05-04 16:45:04    
我有话要说
暂无人分享评论!