[BZOJ 3157] 国王奇遇记

Link:

BZOJ 3157 传送门

Solution:

题意：求解$sum_{i=1}^n m^i cdot {i^m}$

$O(m^2)$做法：

定义一个函数$f[i]$，$f[i]=sum_{i=1}^n k^i cdot {m^k}$

$(m-1)cdot f(i)=sum_{k=1}^n k^i cdot m^{k + 1} - sum_{k=1}^n k^i cdot m^k$

                          $= sum_{k=1}^{n+1} (k - 1)^icdot m^k - sum_{k=1}^n k^i cdot m^k $

                          $=  n^i cdot m^{n + 1} + sum_{k=1}^n m^k sum_{j = 0}^{i - 1} {i choose j} cdot (-1)^{i - j} cdot k^j $

                          $=  n^i cdot m^{n + 1} + sum_{j = 0}^{i - 1} {i choose j} cdot (-1)^{i - j} sum_{k = 1}^n k^j cdot m^k $

                          $=  n^i cdot m^{n + 1} + sum_{j = 0}^{i - 1} {i choose j} cdot (-1)^{i - j} cdot f(j) $

接下来只要预处理$C_i^j$，递推即可

Code:

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MAXN=1e3+10;
const int MOD=1e9+7;

ll C[MAXN][MAXN],f[MAXN],n,m,pre,dvs;

ll quick_pow(ll a,ll b)
{
    ll base=a,res=1;
    while(b)
    {
        if(b&1) res=(res*base)%MOD;
        b>>=1;base=base*base%MOD;
    }
    return res;
}

int main()
{
    scanf("%lld%lld",&n,&m);
    if(m==1){printf("%lld",n*(n+1)/2%MOD);return 0;}
    
    pre=quick_pow(m,n+1);dvs=quick_pow(m-1,MOD-2);
    C[0][0]=1;
    for(int i=1;i<=m;i++)
    {
        C[i][0]=1;
        for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
    }
    
    f[0]=(pre-m+MOD)%MOD;(f[0]*=dvs)%=MOD;
    for(int i=1;i<=m;i++)
    {
        pre=pre*n%MOD;f[i]=pre;
        for(int j=0;j<i;j++)
        {
            ll mark=((i-j)&1)?-1:1;
            (f[i]+=mark*C[i][j]*f[j]%MOD)%=MOD;
        }
        (f[i]+=MOD)%=MOD;(f[i]*=dvs)%=MOD;
    }
    printf("%lld",f[m]);
    return 0;
}

Review:

此题的加强版：BZOJ 3516/BZOJ 4126

最后一题要用到$O(m)$的算法，然而我并不能看懂

Resources:

http://blog.miskcoo.com/2014/06/bzoj-3157

http://blog.miskcoo.com/2015/08/special-polynomial-linear-interpolation

http://trinkle.blog.uoj.ac/blog/478

杜教论文：http://www.docin.com/p-638538589.html

也许先补一补多项式定理再多看看具体数学没有公式密集恐惧症了就能看懂了?