BZOJ3157/BZOJ3516 国王奇遇记（矩阵快速幂/数学）

　　由二项式定理，(m+1)^k=ΣC(k,i)*mⁱ。由此可以构造矩阵转移，将mⁱ*i^k全部塞进去即可，系数即为组合数*m。复杂度O(m³logn)，因为大常数喜闻乐见的T掉了。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 202

#define P 1000000007

int n,m,C[N][N];

struct matrix

{

    int n,a[N][N];

    matrix operator *(const matrix&b) const

    {

        matrix c;c.n=n;memset(c.a,,sizeof(c.a));

        for (register int i=;i<n;i++)

            for (register int j=;j<N;j++)

                for (register int k=;k<N;k++)

                c.a[i][j]=(c.a[i][j]+1ll*a[i][k]*b.a[k][j]%P)%P;

        return c;

    }

}f,a;

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj3157.in","r",stdin);

    freopen("bzoj3157.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read()+,m=read();

    C[][]=;

    for (int i=;i<=m;i++)

    {

        C[i][]=C[i][i]=;

        for (int j=;j<i;j++)

        C[i][j]=(C[i-][j-]+C[i-][j])%P;

    }

    a.n=m+;

    for (int i=;i<=m;i++)

        for (int j=;j<=i;j++)

        a.a[j][i]=1ll*m*C[i][j]%P;

    a.a[m][m+]=a.a[m+][m+]=;

    f.n=;f.a[][]=;

    for (;n;n>>=,a=a*a) if (n&) f=f*a;

    cout<<f.a[][m+];

    return ;

}

　　考虑更神的完全想不到的推导：（直接搬了）

就可以做到O(m²)了。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 2010

#define P 1000000007

int n,m,C[N][N],f[N];

int ksm(int a,int k)

{

    if (k==) return ;

    int tmp=ksm(a,k>>);

    if (k&) return 1ll*tmp*tmp%P*a%P;

    else return 1ll*tmp*tmp%P;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj3157.in","r",stdin);

    freopen("bzoj3157.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read();

    C[][]=;

    for (int i=;i<=m;i++)

    {

        C[i][]=C[i][i]=;

        for (int j=;j<i;j++)

        C[i][j]=(C[i-][j-]+C[i-][j])%P;

    }

    if (m==) {cout<<(1ll*n*(n+)>>)%P;return ;}

    f[]=1ll*m*(ksm(m,n)-)%P*ksm(m-,P-)%P;

    for (int i=;i<=m;i++)

    {

        f[i]=1ll*ksm(n,i)*ksm(m,n+)%P;

        for (int j=;j<i;j++)

        if (i-j&) f[i]=(f[i]-1ll*C[i][j]*f[j]%P+P)%P;

        else f[i]=(f[i]+1ll*C[i][j]*f[j]%P)%P;

        f[i]=1ll*f[i]*ksm(m-,P-)%P;

    }

    cout<<f[m];

    return ;

}

　　甚至可以做到O(m)。不觉得能看懂了。