Article From:https://www.cnblogs.com/newera/p/9130809.html

Link:

BZOJ 3157 Transmission gate

Solution:

Meaning: solving $\sum_{i=1}^n m^i \cdot {i^m}$

 

$O(m^2)$Practice:

Define a function $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)^i\cdot 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) $

As long as the $C_i^j$is preprocessed, the recursion will be

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:

A strengthened edition of this problem: BZOJ 3516/BZOJ 4126

The last one is an algorithm to use $O (m) $.But I can’t understand it.

 

Resources:

BZOJ-3157. 国王奇遇记

特殊多项式在整点上的线性插值方法

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

Du religion thesis: http://www.docin.com/p-638538589.html

 

Maybe fill in a polynomial theorem first and look at more concrete mathematics.There’s no formula – intensive phobiaCan you understand it?

 

Similar Posts:

Link of this Article: [BZOJ 3157] King’s Adventures

Leave a Reply

Your email address will not be published. Required fields are marked *