Hackerrank Coprime Power Sum

Coprime Power Sum传送门
题目大意：计算$displaystyle sum_{i=1}^m{[i%s[j]!=0|forall s[j]in S]i^K}$，其中$|S|=n,gcd(s[i],s[j])=1|ineq j$
如果$n=0$，那么我们就可以用普通的伯努利数在$O(K^2)$的时间内解决，而现在的问题是有一些元素对答案贡献为0，由于贡献为0的元素都是倍数的形式，而且题目中两两互质为我们提供了便利，所以我们来考虑容斥！
对于某一个数$p$来说，它的倍数在答案里的形式为$p^k+(2*p)^k+(3*p)^k+...+(lfloorfrac{m}{p} rfloor*p)^k=p^k*(1^k+2^k+3^k+...+{lfloorfrac{m}{p} rfloor}^k)$，又是一个伯努利数！
那么容斥的最终形式应该为“总的计算值-一个数的倍数的贡献+两个数的倍数的贡献-…”，（假设$f[x]=displaystyle sum_{i=1}^x{i^K}$）也就差不多是$displaystyle f[m]-sum_{i=1}^n{s_i^K*f[frac{m}{s_i}]}+sum_{i=1}^{n}sum_{j=1}^{n}[ineq j]s_i^Ks_j^K*f[frac{m}{s_is_j}]...$（实在写不动了，大家应该都明白吧。。。），所以我们不妨考虑依次加入集合中的每一个数，分步进行容斥，这样的话考虑新加入一个数会怎样影响答案呢？
考虑到$displaystyle lfloorfrac{n}{ab}rfloor=lfloorfrac{lfloorfrac{n}{a}rfloor}{b}rfloor=lfloorfrac{lfloorfrac{n}{b}rfloor}{a}rfloor$，我们经过一些划式子考虑新加入元素在容斥里的系数，由于容斥是一个和式的形式，新加入元素位于序列末尾，所以其实只前的系数仍然是一个容斥的和式的形式！事实上设$f[i][j]$表示考虑序列中前$i$个数，伯努利数中最大数的值域（指的是先不考虑容斥减掉的那一部分）是$j$时的结果，那么最终答案即为$f[n][m]$，通过容斥得到转移$f[i][j]=f[i-1][j]-s_i^K*f[i-1][lfloor frac{j}{s_i}rfloor]$，然后在一定范围内（如取$10^5$）记忆化搜索就好了。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=110;
const int M=200000;
const ll mod=1000000007LL;
int Q,n,K;ll m,a[N],b[N],C[N][N],inv[N],g[N][200100];
ll power(ll a,ll b)
{
    ll ans=1;a%=mod;
    for (;b;b>>=1,a=(a*a)%mod)
    if(b&1)ans=(ans*a)%mod;
    return ans;
}
void prework()
{
    C[0][0]=1;
    for (int i=1;i<N;++i)
    {
        C[i][0]=C[i][i]=1;
        for (int j=1;j<i;++j)
        C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }
    inv[1]=1;
    for (int i=2;i<N;++i)inv[i]=(mod-mod/i)%mod*inv[mod%i]%mod;
}
ll f[N];
ll get(ll m,int K)
{
    ll ans=(m%mod+1)*(m%mod+1)%mod;
    f[0]=m%mod;f[1]=((m%mod*(m%mod+1))%mod*inv[2])%mod;
    for (int i=2;i<=K;++i)
    {
        ans=(ans*(m%mod+1))%mod;f[i]=(ans-1)%mod;
        for (int j=0;j<i;++j)
        f[i]=(f[i]-C[i+1][j]*f[j]%mod+mod)%mod;
        f[i]=f[i]*inv[i+1]%mod;
    }
    return f[K];
}
ll ss(int i,ll j)
{
    if(j<=M&&g[i][j]!=-1)return g[i][j];if(!j)return (K==0);
    if(!i)
    {
        //ll ans=get(j,K);printf("%d %I64d %I64dn",i,j,ans);
        if(j<=M)return g[i][j]=get(j,K);
        else return get(j,K);
    }
    if(a[i]>j)return ss(i-1,j);
    ll ans=(ss(i-1,j)%mod-b[i]*ss(i-1,j/a[i])%mod+mod)%mod;
    if(j<=M)g[i][j]=ans;//printf("%d %I64d %I64dn",i,j,ans);
    return ans;
}
int main()
{
    prework();
    for(scanf("%d",&Q);Q;--Q)
    {
        scanf("%d%d%lld",&n,&K,&m);
        memset(g,0xff,sizeof(g));
        for (int i=1;i<=n;++i)scanf("%lld",a+i);
        for (int i=1;i<=n;++i)b[i]=power(a[i],K);
        //for (int i=1;i<=n;++i)printf("%I64dn",b[i]);
        printf("%lldn",ss(n,m));
    }
    return 0;
}

总结：
1、容斥的复杂度不一定是$2^n$，因为这其中有可能可以划出来一个子问题
2、代码能力有待加强。。。power里居然忘了先取模了

最后

以上就是现代寒风为你收集整理的Hackerrank Coprime Power Sum的全部内容，希望文章能够帮你解决Hackerrank Coprime Power Sum所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。