别问我为什么这么现在才写10.29的题
10.29每日一题
很简单的一道动态规划题，没什么好解释的。
但是鄙人此前未接触过动态规划，所以在看出来是动态规划题后想着有没有别的办法。
很自然的想到能否从数学上找到通解。
将题意抽象一下，要求大致为对于一个大小为n的数组，为没一个下标位置填入1~m中的一个数，无次数限制，并且在填充完毕后要有恰好k个元素与前一个元素不相等。
受高中记忆刺激，觉得可以从排列组合的角度考虑。
对于任意一个元素，若要求其与前一个元素不相等，则该元素可有（m-1）种选择；而对于k个元素，可以从剩余（n-1）个元素中（题意要求不考虑第一个元素）选取k个元素，即指定这k个元素与前一个元素不相等，那么计算公式则为C(n-1,k)k(m-1)。
考虑到n<=2000，包会爆unsigned long long，我还去学了下取模的快速幂和逆元，但是并没有什么卵用，连样例都没过。
然后想是不是没考虑第一个砖块的颜色，然后往代码里加了“*m”，距离答案是接近了些，但是仍然并没有什么卵用。
想打牌大半夜没想明白终于去写动态规划了，写了不到一个小时就过了。
做题最大的幻觉就是我能AC