ARC058D
首先有一个 \(n\times m\) 的矩阵,从左上走到右下的方案数是 \(C_{n+m-2}^{n-1}\).
考虑把原图切分成两个矩阵。(左上和右整边)
计算出走到左上角的矩阵边上每个点的方案数,再乘上这个点走到右下的方案数,求和即可。
ARC058E
发现题目条件中有“存在”字眼,非常容易重复计数,所以我们考虑反面。
总方案数是 \(10^n\),再减去完全不满足条件的即为答案。
看见 \(x+y+z\le 17\) 考虑状压。
设 \(f(n,S)\) 表示已经考虑到 \(n\) 位,状态为 \(S\) 的方案数、
我们如何表示这个 \(S\) 呢?
我们首先想到可以把每个位置的数都在 \(s\) 中表示出来,但可惜数字可以重复,就不能表示。
所以我们可以把 \(S\) 表示为以 \(i\) 结束每个区间的和,可以用二进制表示。
这样如何这个和中同时出现了 \(z,y+z,x+y+z\),就要排除掉。
那么如何转移呢?假设现在加入第 \(i\) 位的数为 \(d\),\(i-1\) 的状态为 \(s\).
新的状态是把 \(s\) 二进制下左移 \(d\) 位,再把第 \(d\) 位设成 \(1\) 即可。
ARC059E
看到很多求和被震慑住了。
考虑 dp,设 \(f_{i,j}\) 表示前 \(i\) 位总共发了 \(j\) 颗糖果。
\(f_{i,j}=\sum f_{i-1,k}\cdot \sum_{t=A_i}^{B_i}(t^{k-j}\).