Contents

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?