循环矩阵的快速幂（bzoj 2510: 弱题）
题名可以。。先考虑概率dp：dp[x][y]表示第x个回合后，标号为y的小球的期望个个数，那么有直接转移的话，复杂度是O(nk)的，肯定会超时，不过还好这个递推式显然能转化成矩阵假设n只有4，那么有递推这样复杂度就降为(n^3logk)了，但n有1000那么大，还是超时。。。但仔细看这个矩阵可以发现一个特点：它的每一行都是上一行往右移动一位得到的不但如此，这
典雅鞋垫
他的归档
热门文章
6
