一个组合计数比较好的题。

恰好一次都不出现的方案数，其实可以容斥成“出现至少 $k$ 次”的方案数（下文表示为 $f_k$）,具体的，可以表示为 $\sum_{i=0}(-1)^if_{i}$，简单容斥不在阐述。

对于至少出现 $k$ 次的方案数，其实可以先生成 $k$ 个段，然后插入到最终的序列里，把每个段缩成一个位置，原本有 $n$ 个位置，$4k$ 个位置被缩进段了，$k$ 个段缩成了一个位置，还剩下 $n-4k+k=n-3k$ 个位置，要选 $k$ 个位置，就是 $C_{n-3k}^k$。

对于剩下的部分，其实就是求出将四种数填满 $n-4k$ 个位置，且剩下每种数都不超过 $a/b/c/d-k$ 次。下文方便讨论，$n\gets n-4k,a,b,c,d$ 各自减去 $k$。

对于 $a+b+c+d=n$ 的情况，实际上是多重集的排列数，即 $\frac{n!}{a!b!c!d!}$。

对于 $a+b+c+d\ge n$ 的情况，实际上可以枚举 $a'\le a,b'\le b,c'\le c,d'\le d$，满足 $a'+b'+c'+d'=n$，然后产生 $\frac{n!}{a'!b'!c'!d'!}$ 的方案，实际上做四次卷积即可解决，这个做法需要外层枚举一个 $k$，内层做卷积，复杂度为 $O(n^2\log n)$。

实际上一个更优的做法，枚举 $x=a'+b'$，则 $n-x=c'+d'$，枚举 $y=a'$，则 $x-y=b'$，注意到 $a'\in [0,a],b'\in [0,b]$，则对于 $y$ 合法取值的限制实际上是和 $x$ 相关的某个区间，可以 $O(1)$ 算法，对于 $c'+d'$ 的部分同理，所以只需要枚举一个 $k$，枚举一个 $x$，然后预处理出组合数的前缀和即可 $O(1)$ 回答，时间复杂度为 $O(n^2)$。

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

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

const int N = 5 * 1e5 + 5;
ll a[N], b[N], ans, n, k;
struct node{
	ll v;
	int cnt;
	bool operator>(const node& o)const{
		if(v != o.v) return v > o.v;
		return cnt < o.cnt;
	}
};

int check(ll mid){
    priority_queue<node, vector<node>, greater<node>> A;
    priority_queue<node, vector<node>, greater<node>> B;
    int cnt = 0;
    ans = 0;
    for(int i = 1;i <= n;i ++){
        A.push({a[i] + mid, 1});
        node op1 = {A.top().v + b[i], A.top().cnt};
        node op2 = B.empty() ? node{(ll)2e18, 0} : node{B.top().v + b[i], B.top().cnt};
        bool flag = (op1.v < op2.v) || (op1.v == op2.v && op1.cnt > op2.cnt);
        node chose = flag ? op1 : op2;
        if(chose.v <= 0){
            ans += chose.v;
            cnt += chose.cnt;
            if(flag) A.pop();
            else B.pop();
            B.push({-b[i], 0});
        }
    }
    return cnt;
}

int main(){

	cin >> n >> k;

	for(int i = 1;i <= n;i ++) {
		cin >> a[i];
	}

	for(int i = 1;i <= n;i ++){
		cin >> b[i];
	}

	ll l = -1e15, r = 1e15, C = r;
	while(l <= r){
		ll mid = (l + r) >> 1;
		if(check(mid) >= k){
			C = mid;
			l = mid + 1;
		}
		else{
			r = mid - 1;
		}
	}
	check(C);
	cout << ans - k * C << '\n';
	return 0;
}

#include<iostream>
using namespace std;

#define int long long
const int M = 998244353;
const int K = 305;
const int N = 2 * 1e5 + 5;
int C[K][K];
int a;
int S[K];
int n, k;

int qpow(int a, int b){
	int res = 1;
	while(b){
		if(b & 1) (res *= a) %= M;
  		(a *= a) %= M;
		b >>= 1;
	}
	return res;
}

void init(){
	for(int i = 0;i <= k;i ++){
		C[i][0] = 1;
		for(int j = 1;j <= i;j ++){
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % M;
		}
	}
}

signed main(){
	
	cin >> n >> k;
	
	for(int i = 1;i <= n;i ++){
		cin >> a;
		int cnt = 1;
		for(int x = 0;x <= k;x ++){
			S[x] = (S[x] + cnt) % M;
			cnt = (cnt * a) % M;
		}
	}
	
	init();
	
	
	for(int x = 1;x <= k;x ++){
		int ans = 0;
		for(int i = 0;i <= x;i ++){
			ans = (ans + (C[x][i] * S[i]) % M * S[x - i] % M) % M;
		}
		ans = (ans + M - qpow(2, x) * S[x] % M) % M;
		cout << ans * qpow(2, M - 2) % M << '\n';
	}
	
	
	
	return 0;
}

淘汰赛：区间最大值贪心解法

一、 题目大意

• 核心描述：

一共有 2n 个国家参加单场淘汰赛，两两配对比赛，能力值高的一方必胜，一直比赛直到决出冠军。比赛顺序：1 和 2 比、3 和 4 比…… 相邻编号两两对决，胜者晋级继续淘汰赛。已知所有国家的能力值互不相同，求最终亚军的国家编号

• 样例说明：

样例输入 n=3，总共有 23=8 个国家。8 个国家能力依次为：1 号：4，2 号：2，3 号：3，4 号：1，5 号：10，6 号：5，7 号：9，8 号：7整个赛程里冠军是 5 号，和冠军在决赛对战的对手就是亚军，也就是1 号，所以输出 1

二、 思路解析（核心部分）

第一层：解题基石

• 贪心思想 + 简单遍历找最大值：

本题不需要模拟完整淘汰赛全过程，仅用基础遍历即可解决

• 选择原因：

1.淘汰赛的赛程结构是严格的完全二叉树，所有队伍被均匀分成左右两个半区

2.冠军必然是两个半区各自的最强者之一

3.亚军一定是另外一个半区里的最强队伍

4.数据范围 n≤7，总人数最多 2^7=128，数据极小，暴力遍历完全足够

第二层：思维脉络

• 关键步骤拆解：

1.计算总参赛队伍数量:tot=2^n

2.将所有队伍平均划分为左半区、右半区两部分

3.分别遍历两个半区，找出左半区能力最强的编号、右半区能力最强的编号

4.两个最强队伍中，能力较弱的那一个，就是最终亚军

• 状态定义：

本题无动态规划，无需 DP 数组定义

• 核心公式/推导：

可设：

maxL = 左半区最大能力值，idL = 对应编号

maxR = 右半区最大能力值，idR = 对应编号决赛对决

则：

max(maxL,maxR) 对应编号为冠军

min(maxL,maxR) 对应编号为亚军

第三层：难点与陷阱

• 本题的易错点：

1.浮点数精度使用错误：使用 pow(2,n) 计算队伍总数，pow 是浮点函数，会出现 128 变成 127.9999 的误差，导致数组越界

2.错误模拟全程比赛：当一层层模拟晋级时，代码写复杂还容易写错

3.混淆能力值和国家编号，只存数值忘记记录原始编号

4.数组下标混乱，左右半区分割错误

• 你是如何思考的：

观察淘汰赛树形结构发现规律：亚军只会是决赛输家，而决赛双方分别是左右两大区的最强者，因此完全不需要模拟全程比赛，只需要找两个大区最大值，弱者即为答案，思路大幅简化。

三、 代码实现

• 代码：

  #include<bits/stdc++.h>
  using namespace std;
  
  int main()
  {
      freopen("knockout.in","r",stdin);
      freopen("knockout.out","w",stdout);
      ios::sync_with_stdio(false);
      cin.tie(0);
      
      int n;
      cin >> n;
      int total = 1 << n;    // 等价于 2^n，整数位运算，无浮点精度误差
      int half = total / 2; // 左右半区分界线
      
      int val[130]; // 下标代表国家编号，值代表能力
      for(int i = 1; i <= total; i++)
      {
          cin >> val[i];
      }
  
      // 寻找左半区(1~half)能力最强的编号
      int maxL = -1, idL = 0;
      for(int i = 1; i <= half; i++)
      {
          if(val[i] > maxL)
          {
              maxL = val[i];
              idL = i;
          }
      }
  
      // 寻找右半区(half+1~total)能力最强的编号
      int maxR = -1, idR = 0;
      for(int i = half + 1; i <= total; i++)
      {
          if(val[i] > maxR)
          {
              maxR = val[i];
              idR = i;
          }
      }
  
      // 两者中能力更小的就是亚军
      if(maxL < maxR) cout << idL;
      else cout << idR;
      
      return 0;
  }
  

• 复杂度分析：
  • 时间复杂度：O(2^n)

  原因：仅遍历一遍所有参赛国家寻找最大值，每个元素访问一次。

  • 空间复杂度：O(2^n)

  原因：用数组存储所有国家的能力值，数组大小为 2^n

四、 总结与反思（升华部分）

• 收获与心得：

1.透过赛程结构找规律，不用死板模拟全过程，淘汰赛树形结构有固定结论：亚军是决赛对手，即另一半区最强者

2.规避 pow() 函数浮点误差的技巧：用位运算 1<<n 计算 2n

3.理解单胜者淘汰赛、完全二叉树比赛模型的通用性质

• 举一反三：

本题结论可以迁移到所有相邻配对、强者必胜、单败淘汰赛题目：

1.求决赛两支队伍

2.求四强、八强分别是谁

3.同类体育竞赛赛程推理题目。

• 待优化空间：

1.可以封装函数实现通用区间最大值查找，代码复用性更高

2.可以扩展写法，模拟完整每一轮晋级过程，输出每一轮晋级名单，验证规律

3.若题目改为弱者获胜，只需修改大小比较符号即可，整体思路不变。

五、 推荐题目

• 603. 网球赛 http://172.30.1.3/cogs/problem/problem.php?pid=pmzSJieaj

3139. [HSOI 2019] HS的新题 - COGS

显然随机数据, 考虑珂朵莉树.

以下均在 auto itr = split(r + 1), itl = split(l);的基础上进行.

注意要开 long long, 以及, 所有操作后得到的答案均为模运算后结果, 否则这个题写不成.

操作 1

直接 assign 即可.

操作 2

遍历 $itl \le it <itr$, 用逆元计算每一个颜色段 $/x$ 的值即可.

操作 3

遍历 $itl \le it <itr$, 计算每一个颜色段 $*x$ 即可.

操作 4

遍历 $itl \le it <itr$, 如果 $x \le v \le y$, then cnt++.

操作 5

遍历 $itl \le it <itr$, 统计总和, 再 assign 平均值即可.

操作 6

遍历 $itl \le it <itr$, map 统计每个数个数, 再遍历一遍 map 即可.

操作 7

遍历 $itl \le it <itr$, 全部数字插入到一个 set 中, set 的值就是答案.

操作 8

遍历 $itl \le it <itr$, 使用异或空间线性基处理即可.