A. 聖誕樹

2021.11.17模擬賽部分題解_#include

代碼 

#include <bits/stdc++.h>
using namespace std;

namespace myb {
	
	using ll = long long;
	const int N = 2e5 + 10;
	const int Mod = 998244353;
	
	int a[N];
	
	void main() {
		int n;
		cin >> n;
		for (int i = 1;i <= n;i++) cin >> a[i];
		
		ll ans = 1;
		for (int i = 1;i <= n ;i++) ans = (__int128)ans * a[i] % Mod;
		ll S = 0;
		for (int i = 1;i <= n;i++) S += a[i] - 1;
//		cout << S << " " << ans << "\n";
		for (ll i = S;i > S - n + 2;i--) ans = (__int128)ans * i % Mod;
		cout << ans;
		// \prod a_i S!/(S - n - 2)!
	}
}

int main() {
	myb::main();
	return 0;
}

B. 序列

我們從值域的角度去想，如果我當前將所有大於 i 的數已經加進去了，現在我們要將所有的 i 插入這個序列中。

考慮如果現在我有 j 個連續段，那麼如果我插入一個 i 不使段數增加，那麼必須插在段尾，否則 i 會使段數增加。

我可以枚舉不使段數增加的 i 有 x 個，剩下 \(a_i - x\) 個要插進原本連續段的兩個數中間去，使連續段增加 \(a_i - x\)

因為可以有兩個 i 插入一個縫中，所以我們考慮插板法。

一共 \(a_i - x\) 個數，\(\sum_{t = i}^n a_t - j + x\)

則方程為

f[i][j + a[i] - x] += f[i][j] * C(j, x) * C(sum[i + 1] - j + x, sum[i + 1] + a[i] - j)

代碼 

#include <bits/stdc++.h>
using namespace std;

namespace myb {
	
    #define int long long
	using ll = long long;
	const int N = 55;
	const int Mod = 1e9 + 7;
	
	int a[N];
	
	ll f[N][N * N], C[3005][3005], sum[N];
	
	void main() {
        // cout << 114514;
		int n, k;
		cin >> n >> k;
		for (int i = 1;i <= n;i++) cin >> a[i];
		
        C[0][0] = 1;
		for (int i = 1;i <= 3000;i++) {
			C[i][0] = 1;
			for (int j = 1;j <= min(3000ll, i);j++) {
				C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
				C[i][j] %= Mod;
			}
		}
		
		for (int i = n;i >= 1;i--) sum[i] = sum[i + 1] + a[i];
//		cout << C[4][2] << '\n';
		
		f[n][a[n]] = 1;
		for (int i = n - 1;i >= 1;i--) {
			for (int j = 1;j <= k;j++) {
				for (int x = 0;x <= min(j, a[i]);x++) {
					if (j + a[i] - x > k) continue;
					if (sum[i + 1] + a[i] - j < 0) continue;
					if (sum[i + 1] + x - j < 0) continue;
					f[i][j + a[i] - x] += f[i + 1][j] * C[j][x] % Mod * C[sum[i + 1] + a[i] - j][sum[i + 1] - j + x] % Mod;
					f[i][j + a[i] - x] %= Mod;
				}
			}
		}
		cout << f[1][k];
	}
}

signed main() {
	freopen("seq.in", "r", stdin);
	freopen("seq.out", "w", stdout);
	myb::main();
	return 0;
}