传送门
Table of Contents
Problem A. Three Cards
取任意张也可做。排序两次，第一次用数字排序，第二次用字符串排序（但是要修改一下字典序的定义，不存在的字符取无穷大）。
Problem B. Plus and AND
题解里说二分，但是应该没有人会去写二分吧（复杂度一样）。。。
当然是去写按位贪心。。。每次确定第 i 位是否可以为 1，那么对于每个数需要求出与当前目标的距离。。
难点在于这个距离函数，需要各种讨论。
当然大牛们都是用位运算一行就把距离函数写出来的囧。。
Problem C. Even XOR
Problem E. Simple Speed
计数，问有多少种满足以下条件的整数序列：
1. 每个数字出现的次数恰好为 Ai。
2. 相邻位置的差的绝对值恰好为 1。
个人觉得这个 dp 非常的优雅！
首先不考虑条件 2，那么就是 多项式系数。
考虑条件 2，我们似乎可以暴力 dp…
dp[i][j] 表示前 i 位，末尾为 j 的方案数，
但这个显然不可行。。因为我们没法记录每个数字当前还剩多少。。
所以核心是我们要避免去讨论当前状态里每个数字还剩多少。。。有办法吗？
答案是有的！逐层推进 就行，也就是用数字的大小划分阶段。。。
那么一开始显然只有。。
1 1 1
下一层，我们要把 2 插入 1 之间的空隙里。。。不妨考察两个边界情况。。。
最少需要 2 个 2。。。变成。。
1 2 1 2 1
最多似乎可以有 4 个 2。。。变成。。
2 1 2 1 2 1 2
其实不止。。因为我们还可以往两边任意的继续加 2。
只不过中间的这个 {2 1 2 1 2 1 2} 现在是一个整体，而且它现在等价于上一轮的一个 {1}。。。这样我们似乎找到了可以描述的状态。。序列的序列。。
比如如果我们有 6 个 2，那么这一轮我们可以是。。
{2} {2 1 2 1 2 1 2} {2}
{2 1 2 1 2 1 2} {2} {2}
{2} {2} {2 1 2 1 2 1 2} …
这三种情况，都和第一轮的 {1} {1} {1} 是等价的。。。
所以我们每一层的任务，就是连接这些子序列之间的空隙，并生成一些新的空隙。
或者更简单的理解。。。下一轮最后等价于一些 {3} {3} {3} 。。。然后我们用上一层的序列，去连接这一层的序列。。。简单组合数即可。。
难点是需要讨论两侧的状态，因为它们可能不可参与拼接。。
所以状态就是 dp[i][j][k]。。当前阶段为 i，两侧可拼接 j 次，中间还有 k 个位置可拼接。。
。。。
分析状态转移，我们会发现这个状态空间非常稀疏，直接开个 map 跑 dp 即可。
#include <lastweapon/number>
using namespace lastweapon;
const int N = int(2e5) + 5;
int A[N]; Int F[N]; map<int, Int> dp[N][3];
int n;
inline Int C(int n, int m){
return F[n]/(F[m]*F[n-m]);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
MOD = 998244353;
F[0] = 1; FOR(i, 1, N) F[i] = F[i - 1] * i;
RD(n); REP(i, n) RD(A[i]);
dp[0][2][A[0]-1] = 1;
FOR(i, 1, n) REP(a, 3) for(auto it: dp[i-1][a]){
int x = it.fi; Int u = it.se;
FOR_1(b, max(0, 1-x), min(a, A[i]-x)) {
int y = A[i]-x-b;
dp[i][b][y] += u * C(A[i]-1, y) * C(a, b);
}
}
Int z = 0; REP(i, 3) z += dp[n-1][i][0];
OT(z);
}
