bzoj3157 国王奇遇记 && bzoj 3516 国王奇遇记加强版

ShinriiTin posted @ 2015年6月11日 16:47 in 未分类 with tags 数论 , 653 阅读

求∑_i(i>0&&i<=n)i^m*mⁱmod 1000000007

令f_k=∑_i(i>0&&i<=n)i^k*mⁱ

两边同乘(m-1),整理得:(m-1)f_k=n^k*mⁿ⁺¹+∑_i(i>0&&i<=n)mⁱ*[(i-1)^k-i^k]

用二项式定理展开(i-1)^k,整理得:(m-1)f_k=n^k*mⁿ⁺¹+∑_i(i>0&&i<=n)m_i*∑_j(j>=0&&j<k)C(k,j)*(-1)^k-j*i^j

交换一下两个循环的位置,整理得(m-1)f_k=n^k*mⁿ⁺¹+∑_j(j>=0&&j<k)C(k,j)*(-1)^k-j*∑_i(i>0&&i<=n)i^j*mⁱ

好像发现了什么熟悉的东西。。。

(m-1)f_k=n^k*mⁿ⁺¹+∑_j(j>=0&&j<k)C(k,j)*(-1)^k-j*f_j

这样就能O(m²)计算了

这两题做法一模一样。。。我就贴个3157的代码吧

My Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58	`#include <stdio.h>` `#include <string.h>` `#include <algorithm>` `using` `namespace` `std;` `const` `int` `MAXN=205;` `const` `int` `Mod=1e9+7;` `typedef` `long` `long` `ll;` `int` `n,m;` `inline` `ll qpow(ll x,int` `k){` `ll ans=1;` `for(;k;x=xx%Mod,k>>=1)` `if(k&1)ans=ansx%Mod;` `return` `ans;` `}` `int` `C[MAXN][MAXN];` `inline` `void` `Init(){` `scanf("%d%d",&n,&m);` `for(int` `i=1;i<=m;++i){` `C[i][0]=C[i][i]=1;` `for(int` `j=1;j<i;++j){` `C[i][j]=(C[i-1][j]+C[i-1][j-1])%Mod;` `}` `}` `}` `int` `ans,s[MAXN];` `inline` `void` `Solve(){` `int` `inv=qpow(m-1,Mod-2);` `int` `nn=1,mm=qpow(m,n+1);` `s[0]=(qpow(m,n+1)-m+Mod)inv%Mod;` `for(int` `i=1;i<=m;++i){` `nn=(ll)nnn%Mod;` `s[i]=(ll)nnmm%Mod;` `for(int` `j=0;j<i;++j){` `int` `res=(ll)C[i][i-j]s[j]%Mod;` `if((i-j)&1)s[i]=(s[i]+Mod-res)%Mod;` `else` `s[i]=(s[i]+res)%Mod;` `}` `s[i]=(ll)s[i]inv%Mod;` `}` `printf("%d\n",s[m]);` `}` `int` `main(){` `Init();` `if(m==1){` `ans=((ll)n(n+1)>>1)%Mod;` `printf("%d\n",ans);` `}` `else` `Solve();` `return` `0;` `}`

其实还有个再加强版。。。太神，不会做