牛妹的数学难题

tag：

• 逆元，组合数，前缀记忆
• cf分段1900

题意：

已知一堆序列范围在0 1 2当中
求公式结果

公式如下： ${\sum }_{i_1=1}^n{\sum }_{i_2=i_1+1}^n\mathrm{.}\mathrm{.}\mathrm{.}{\sum }_{i_k=i_{k-1}}^n{\prod }_{j=1}^n{a}_{i_j}\backslash sum\_\{i\_1\; =\; 1\}^\{n\}\{\backslash sum\_\{i\_2\; =\; i\_1+1\}^\{n\}\{...\backslash sum\_\{i\_\{k\}\; =\; i\_\{k-1\}\}^\{n\}\{\backslash prod\_\{j\; =\; 1\}^n\{a\_\{i\_j\}\}\}\}\}$

方案采用枚举组合数的情况，本质上这题可以归结为

num2 = C(sum2,i)//这里表示从所有的2中选i个2的方案数
num1 = C(sum1,k - i)//这里表示从所有的1中选k - i个1的方案数
ans += num1 * num2 * pow(2,i);
//这里所有值的积为pow(2,i),一共有num1*num2种方案。因此答案加上这些

组合数求值这里需要简单的逆元，否则求不出来。具体可以直接看别人的板子 然后这题比较卡常，几次t下来感觉枚举一次方案，逆元的次数最多只能三次，否则会t飞

前缀这里就不过多说明了，能做到这题的人至少应该能熟练使用前缀了.jpg

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e7 + 10;
const int mod = 998244353;
ll q[3];
ll qpow(ll a, ll x) {
	ll res = 1;
	while (x) {
		if (x & 1) res = res * a % mod;
		a = a * a % mod;
		x >>= 1;
	}
	return res;
}
ll q2[maxn];
ll rm[maxn];
ll ne[maxn];
int main() {
	ios::sync_with_stdio(0);
	int n, k;
	cin >> n >> k;
	int tmp = 0;
	q2[0] = rm[0] = 1;
	for (int i = 1; i <= n; i++) {
		cin >> tmp;
		q[tmp]++;
		rm[i] = rm[i-1] * i % mod;
		q2[i] = q2[i - 1] * 2 % mod;
	}
	ll ans = 0;
	ll tm2 = q[2],tm1 = q[1];
	for (int i = 0; i <= k; i++) {
		if ( tm2 >= i && tm1 >= k - i ) {
			ll num1 = (rm[tm2] * qpow(rm[i]*rm[tm2 - i]%mod, mod - 2) % mod);
			ll num2 = (rm[tm1] * qpow(rm[k  - i]*rm[tm1 - k + i]%mod, mod - 2) % mod);
			ans = (ans + num1 * num2 % mod *q2[i]%mod) % mod;
		}
	}
	cout << ans;

}