Atcoder 乱做

这里面有一部分题没有写过代码，不保证完全正确。

ARC061F

第一步转化没想到。但是后面的自己推出来了。

首先你要把它转化成一个序列对吧。

我这边的计数方法和其他人的有点不一样。

那么在这个数列里，\(A\) 会出现 \(n-1\) 次，\(B\) 出现不超过 \(m-1\) 次，\(C\) 出现不超过 \(k-1\) 次。且最后一次出现的一定是 \(A\)。

那么大力枚举序列的长度。再枚举 \(B\) 的出现次数。

\[\begin{aligned}Ans & = \sum_{len=n-1}^{n+m+k-1} 3^{n+m+k-len} \sum_{i} {len-1 \choose n-2} {len-n+1 \choose i}\\& = \sum_{len-n-1}^{n+m+k-1} 3^{n+m+k-len} {len-1 \choose n-2} \sum_{i} {len-n+1 \choose i}\end{aligned} \]

像上面所说，此时的 \(i\) 有限制。\(i \leq m-1\) 且 \(len-(n-1)-i \leq k-1\)。

所以右边实际上是

\[\sum_{i=len-(n-1)-k+1}^{m-1} {len-n+1 \choose i} \]

那么我们记

\[f(l,r,a) = \sum_{i=l}^r {a \choose i} \]

那么我们就想 \(f(l,r,a) \rightarrow f(l+1,r,a+1)\)。

考虑做差

\[\begin{aligned}& \ \ \ \ \ f(l+1,r,a+1) - f(l,r,a)\\& = (\sum_{i=l+1}^r {{a+1 \choose i} - {a \choose i}}) - {a \choose l}\\& = (\sum_{i=l+1}^r {a \choose i-1}) - {a \choose l}\\& = (\sum_{i=l}^r{a \choose i}) - {a \choose l} - {a \choose r}\\& = f(l,r,a) - {a \choose l} - {a \choose r}\end{aligned} \]

然后你就可以愉快地递推了。