P6271 [湖北省队互测2014]一个人的数论

为了方便计算，这里用变量名表示题目中的

求解：

则原式：

自然数幂和是一个次多项式，可以用伯努利数算出系数，不妨记为

由伯努利公式得：

则原式：

令，易知是积性函数，令，则有

则

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=107,mod=1e9+7;
ll qpow(ll a,ll b) {
    ll res=1;
    while(b) {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
ll inv[maxn],fac[maxn];
int B[maxn],f[maxn];
ll C(int n,int m) {
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
void Init_Bernoulli(const int k) {
    B[0]=1;
    for(int i=1;i<=k;++i) {
        ll sum(0);
        for(int j=0;j<i;++j) sum=(sum+C(i+1,j)*B[j])%mod;
        B[i]=(-sum*qpow(C(i+1,i),mod-2)%mod+mod)%mod;
    }
    for(int i=0;i<=k;++i) f[k+1-i]=C(k+1,i)*B[i]%mod*qpow(k+1,mod-2)%mod;
}
void init(const int k) {
    fac[ 0 ] = 1;
    for( int i = 1 ; i <= k ; i ++ ) fac[ i ] = fac[ i - 1 ]*i%mod;
    inv[ k ] = qpow(fac[k],mod-2);
    for( int i = k ; i >= 1 ; i -- ) inv[ i - 1 ] = inv[ i ]*i%mod;
}
int k,w,p[1005];
int sum(int pw) {
    if(pw<0) pw+=mod-1;
    ll res=1;
    for(int i=1;i<=w;++i) res=res*(1-qpow(p[i],pw))%mod;
    return (res+mod)%mod;
}
signed main() {
    cin.sync_with_stdio(false), cin.tie(nullptr),cout.tie(nullptr);
    cin>>k>>w;
    ll ans(0),n=1,x=1;
    for(int i=1,y;i<=w;++i) {
        cin>>p[i]>>y;
        n=n*qpow(p[i],y)%mod;
    }
    init(k+1);
    Init_Bernoulli(k);
    for(int i=1;i<=k+1;++i) {
        x=x*n%mod;
        ans=(ans+f[i]*x%mod*sum(k-i))%mod;
//        cout<<f[i]<<' '<<x<<' '<<sum(k-i)<<'\n';
    }
    cout<<ans<<'\n';
    return 0;
}