【NOIP2017提高A组模拟8.24】早苗

Description:

2<=m<=100,2<=m<=n<=1e16

题解：

n这么大，这种题一看就是矩阵乘法的嘛。

设 fi,j 表示现在长度为i，后j种神风互不相同的方案数。
第一种转移就是当前选的神风和前面的j种都不同，显然有 fi+1,j+1+=fi,j∗(m−j) 。
第二种转移就是当前选的神风和前面的j种中的一种相同，这时候不太好考虑，因为我们不知道新的j’是多少。
这时候需要这么考虑：
假设当前有一个长度为i，后j种神风不同的串，那如果我当前选的的是那j种神风的一种，那么新的j’就恰好会是1-j,于是转移方程就出来了， fi+1,j′+=fi,j(1<=j′<=j)

搞个友矩阵出来优化优化就行了。

时间复杂度： O(m3log n)

Code:

#include<cstdio>
#include<cstring>
#define ll long long
#define fo(i, x, y) for(ll i = x; i <= y; i ++)
using namespace std;

const ll N = 105, mo = 1e9 + 7;

ll n, m, ans, a[N][N], b[N][N], c[N][N];

int main() {
scanf("%lld %lld", &n, &m);
    m --;
    fo(i, 1, m) {
        fo(j, 1, i) b[i][j] = 1;
if(i < m) b[i][i + 1] = m + 1 - i;
    }
    fo(i, 1, m) a[i][i] = 1;
    n --;
while(n > 0) {
if(n & 1) {
memset(c, 0, sizeof(c));
            fo(k, 1, m) fo(i, 1, m) fo(j, 1, m) c[i][j] += a[i][k] * b[k][j] % mo;
            fo(i, 1, m) fo(j, 1, m) a[i][j] = c[i][j] % mo;
        }
        n >>= 1;
memset(c, 0, sizeof(c));
        fo(k, 1, m) fo(i, 1, m) fo(j, 1, m) c[i][j] += b[i][k] * b[k][j] % mo;
        fo(i, 1, m) fo(j, 1, m) b[i][j] = c[i][j] % mo;
    }
    fo(j, 1, m) ans = (ans + (m + 1) * a[1][j]) % mo;
printf("%lld", ans);
}