【bzoj 3601】一个人的数论（莫比乌斯反演+伯努利数）

题解：

　　（吐槽：网上题解那个不严谨猜测真是没谁了……关键是还猜得辣么准……）

　　直接化简到求和那一段：

$f_{d}(n)=\sum_{t|n}\mu(t)t^{d}\sum_{i=1}^{\frac{n}{t}}i^{d}$

$设S_{d}(T)=\sum_{i=1}^{T}i^{d}$

　　那这个是什么呢？伯努利数（我会说我百度找到的吗……）

百度

递推公式

$s_{p}(T)=\sum_{i=1}^{p+1}\frac{(-1)^{p+1-i}C_{p+1}^{i}B_{p+1-i}}{p+1}n^{i}$(这个是百度那个公式化过来的)

　　然后$n^{i}$前面那一堆玩意就是网上题解的$a_{i}$。

　　接下来的化简我就不解释了……http://www.cnblogs.com/jianglangcaijin/p/4033399.html

　　然后我们只要求出C和B这题就没了。（貌似可以把d的范围再扩10倍233）

代码：

 #include<cstdio>

 using namespace std;

 typedef long long ll;

 const ll mod=1e9+;

 const int N=;

 inline ll read(){

     ll s=,k=;char ch=getchar();

     while(ch<''|ch>'')    ch=='-'?k=-:,ch=getchar();

     while(ch>&ch<='')    s=s*+(ch^),ch=getchar();

     return s*k;

 }

 inline ll powmod(ll a,ll b){

     ll ans=;

     if(b<)

         return powmod(powmod(a,mod-),-b);

     a%=mod;

     while(b){

         if(b&) ans=ans*a%mod;

         b>>=;a=a*a%mod;

     }return ans;

 }

 ll w,d;

 ll p[N],pk[N];

 ll tot=;

 inline ll calc(int n){

     ll t=powmod(tot,n);

     for(int i=;i<=w;i++){

         t=t*(1ll-powmod(p[i],d-n))%mod;

     }

     if(t<) t+=mod;

     return t;

 }

 ll c[][],b[];

 int main(){

     d=read(),w=read();

     ll n=w;

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

         p[i]=read(),pk[i]=read();

         tot=tot*powmod(p[i],pk[i])%mod;

     }

     c[][]=;

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

         c[i][]=;

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

             c[i][j]=(c[i-][j]+c[i-][j-])%mod;

     }

     b[]=;

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

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

             b[i]=(b[i]+c[i+][j]*b[j])%mod;

         b[i]=b[i]*(-powmod(i+,mod-))%mod+mod;

         b[i]%=mod;

     }

     ll ans=;

     ll inv=powmod(d+,mod-);

     for(int i=;i<=d+;i++){

         ll temp=((d+-i&)?-:)*c[d+][i]*b[d+-i]%mod*inv%mod;

         if(temp==)

             continue;

         temp=temp*calc(i)%mod;

         ans+=temp;

         ans%=mod;

     }

     printf("%lld\n",(ans%mod+mod)%mod);

 }

 /*

 3 2

 2 1

 5 1

 */

巴特西

【bzoj 3601】一个人的数论（莫比乌斯反演+伯努利数）

题解：

代码：

最新文章

热门文章

巴特西

【bzoj 3601】一个人的数论 （莫比乌斯反演+伯努利数）

题解：

代码：

最新文章

热门文章

【bzoj 3601】一个人的数论（莫比乌斯反演+伯努利数）