在更 qwq
17 级整理的部分题目的做题记录。来源：CS Academy
Cube Coloring
题目大意
你有 (n) 种颜料和一个普通的六面骰子，第 (i) 种可以在骰子上最多使用 (a_i) 面。
问有多少种涂色方案使得骰子的相邻两面颜色不同。旋转相同算同种方案。
(1le nle 10^3)
题解
因为有相邻两面颜色不同的要求，使用一种合法方案如存在颜色相同，最多相对的两面颜色相同。
硬分类讨论，除掉旋转同构的方案就行。
Random Nim Generator
题目大意
有一个长度为 (n) 的数组，每个位置可以填 (0sim k) 的一个数，为所有数异或和大于 (0) 的方案数。
(1le nle2 imes10^4,1le kle5 imes10^4)
题解
(f_{i,jwedge k}=sum f_{i-1,j} imes g_k)，当 (0le kle K) 时，(g_k=1)。可以 FWT 加速。
(FWT(g)leftarrow FWT(g)^n) 就只用一次 FWT 了。
Colored Forests
题目大意
给你两个数 (n) 和 (m)，一棵树的每个结点为 (m) 种颜色中的一种，如果一棵树上 (m) 种颜色都出现了，就称这棵树为彩色的。
问 (1sim n) 个有标号的结点组成彩色森林的方案数。
(1le nle10^5,1le mle50)
题解
设 (f_{i,j}) 表示前 (i) 个结点染 (j) 种颜色的方案数：(f_{i,j}=(f_{i-1,j}+f_{i-1,j-1} imes j)) .
设 (g_i) 为将 (i) 个节点组合成彩色的树的方案数：(g_i=f_{i,m} imes i^{i-2}) .
设 (h_i) 为 (i) 个节点组合成彩色森林的方案数：(h_i=sum_{j=0}^ig_j imes h_{i-j} imes C_{i-1}^{j-1}) .
exp 的做法：[By-wrp](等原作者上传到博客 qwq)
101 Palindromes
题目大意
给一个由 (0sim9) 组成的字符串 (S)，问有到多少个子序列满足是回文串且整除 101。
(1le |S|le200)
题解
设 (f_{i,l,r,s}) 为长度为 (i)，位于区间 ([l,r]) 间，数字和 (mod 101) 为 (s) 的方案数：
(f_{i,l,r,s}=f_{i,l,r-1,s} +f_{i.l+1,r,s}-f_{i,l+1,r-1,s}) .
(a_l=a_r) 时，(f_{i,l,r,s}+=f_{i-2,l+1,r-1,s-a_l imes(1+10^{i-1})}) .
然后发现 (i) 只在计算 (s-a_l imes(1+10^{i-1})) 时必不可少，而 (10000equiv1mod101)，所以可以直接压成第一维为 (0sim 3).
Distinct Neighbours
题目大意
给你一个长度为 (n) 的序列 (a)，问有多少种排列方式使得不存在相邻的两个数相同。
(1le nle750,1le a_ile n)
题解
(m) 为出现了多少种不同的数字，令 (siz_i) 表示第 (i) 种数字的出现次数，(s_i=sum_{j=1}^isiz_j) .
设 (f_{i,j}) 为放完前 (i) 种数字，还有 (j) 个空隙左右两边是一样的数字的方案数，答案就是 (f_{m,0}) .
更新大概是这样的： (f_{i,j} imes C_{siz_{i+1}-1}^{k-1} imes C_j^r imes C_{s_i+1-j}^{k-r} ightarrow f_{i+1,j+siz_i-k-r}) .
更快的做法：By-Rayment