小G的ACM之路

题意： 每次将序列中两个数相加再加入序列中，反复操作k次，问k次操作后的序列和最大是多少。 思路： 序列和最大，显然是每次取序列中最大的两个数相加。但是k最大为10亿，实在太大了，所以需要找规律。 输入 3 2 6 3 2 k=1：6 3 = 9 1 * 6 1 * 3 = 9k=2：6 3 6 = 15 2 * 6 1 * 3 = 15k=3：6 3

解析： 很显然矩阵的第一列为： 0 a[1] a[2] a[3] a[4] 我们转化一下，转化为 23 a[1] a[2] a[3] a[4] 3 那么由第一列转移到第二列则为 23*10+3 a[1]+23*10+3 a[2]+a[1]+23*10+3 a[3]+a[2]+a[1]+23*10

解析： 写出f(2),f(3),f(4),f(5) ………可以发先 a b的系数是一系列的fib数列 如果可以求出fib数列 求快速幂就可以了 这样问题就在于如何求fib数列了 很容易想到用矩阵法。 另外 注意在矩阵相乘的时候会溢出 要用long long 如果对1000000007求余的话 依旧会溢出 （如果对它求余就错） 但是可以这样做 利用下

题意： 给一个有向图，从任意点开始，最多走m步，求形成的图案总数。 思路： 令dp[i][j]dp[i][j]表示：走jj步最后到达i的方法数， 则dp[i][j]=∑dp[k][j−1]dp[i][j]=\sum{dp[k][j-1]}，其中k表示：走jj步可以直接到达ii的点。 ans=∑dp[i][j]ans=\sum{dp[i][j]}。 此题的关键在于，如何减少状