arc-116
自以为A了一道精妙的DP题结果被第二道同样思想的DP卡死
D 总和给定下进行NIM必败态计数
给出n、m，表示总共有n堆可空石堆$ {a_i}$，要求满足$\sum a_i = m, \bigoplus a_i=0$，查询这样的序列的个数。
感觉上可以称之为非常经典的题目。
设置dp状态：dp[i]表示n堆石子和为i，异或和为0的序列数量。
状态转移为：
$$dp[2x + k] = \sum dp[x] * (^n_k)$$，k取遍范围内的偶数。
这个状态的转移本质上是用一些更小的情况不重不漏地刻画新的状态。如果当前已知dp[x]，将这n堆石子的二进制表示全部左移一位，再枚举n个最低位有多少个1，就是和为$2*x+k$的一种构造情况。
这种思想跟用最小的素因子来刻画数字之间转化关系有着异曲同工之妙，但我暂时想不到什么形而上的表达形式来统一地刻画这种思考方式，故留坑。
1const int maxn = 5e3 + 10;
2const int M = 998244353;
3
4ll C(int n, int m){
5 m = min(m, n - m);
6 ll ans = 1;
7 for(int i = 1; i <= m; i++){
8 ans = ans * qp(i, M - 2, M) % M;
9 ans = ans * (n + 1 - i) % M;
10 }
11 return ans;
12}
13
14ll dp[maxn];
15ll c[maxn];
16
17int main(){
18 // Fastin;
19 int n, m; scnaf("%d %d", &n, &m);
20 for(int i = 0; i <= n; i++) c[i] = C(n, i);
21 dp[0] = 1;
22 for(int i = 1; i <= m; i++){
23 if(i & 1) dp[i] = 0;
24 else{
25 for(int j = 0; j + j <= i && j + j <= n; j++){
26 dp[i] += c[2 * j] * dp[i / 2 - j] % M;
27 dp[i] %= M;
28 }
29 }
30 }
31 // prt(dp, m + 1, 1);
32 printf("%lld\n", dp[m]);
33 return 0;
34}