容忍因子大于1,结构容忍因子

针对某些题目pddddd反演公式法不太好用的情况 hdu5212: 求 第一步化简柿子： 第二步看注释： 注意：倒着维护dp就是因子容斥 正着维护dp容斥系数是pddddd函数 维护dp本质上是至少变恰好的容斥过程 //求hdu5212sum{i=1~n}{j=1~n}(ai,aj)^2-(ai,aj) n,ai<=1e4;带T //化简一下柿子：ans=sum{i=1~1e4}(d^2-d)*dp[d]//dp[d]: 有多少对(ai,aj)==d//维护cnt[i],有多少个aj是i的倍数//那么dp[i]的初始值为cnt[i]*cnt[i] (乘法定理)//辅助理解：初始值dp[i]=cnt[i]*cnt[i]表示有dp[i]对(at,aj)是i的倍数 //然后因子容斥即可 #include<bits/stdc++.h> #define ll long longusing namespace std;const int mod=1e4+7;int dp[10005];int cnt[10005];int a[10005];int main(){int n;while(~scanf("%d",&n)){ll ans=0;for(int i=1;i<=10000;i++)cnt[i]=0,dp[i]=0;for(int i=1;i<=n;i++)scanf("%d",&a[i]),cnt[a[i]]++;for(int i=1;i<=10000;i++){for(int j=2*i;j<=10000;j+=i)(cnt[i]+=cnt[j])%=mod;}for(int i=10000;i>=2;i--){dp[i]=1ll*cnt[i]*cnt[i]%mod;for(int j=2*i;j<=10000;j+=i)(dp[i]-=1ll*dp[j]+mod)%=mod;ans=ans+(1ll*(1ll*i*i-i+mod)%mod)*dp[i]%mod;ans%=mod;}printf("%I64dn",(ans+mod)%mod);}} CodeForce839D: 子集gcd，嘛，第一步也是先化简柿子 这种柿子也不好用公式法 后面那戳设为dp[d],然后看注释 //CF839D题意：给一个集合A，若子集S的gcd不为1，则做贡献gcd(S)*|S|//问总贡献是多少 ai<=1e6,n<=2e5 //思路：枚举gcd(1e6=>i>=2)，答案就是sum{i=2~1e6}i*dp(i)//dp(i):gcd为i的子集S出现次数*|S|,考虑dp[i]的初值，后面因子容斥 //维护cnt[i]:有cnt[i]个aj满足aj是i的倍数//我们的子集大小|S|可以是1~cnt[i] ，枚举子集大小j： //dp[i]=sum{j=1~cnt[i]}j*C(cnt[i],j)=cnt[i]*2^(cnt[i]-1); #include<bits/stdc++.h>#define ll long long using namespace std;const int mod=1e9+7;int cnt[1000005];int a[1000005];ll dp[1000005];ll ans=0;ll f[1000005];int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]),cnt[a[i]]++;f[0]=1;for(int i=1;i<=1000000;i++){f[i]=1ll*2*f[i-1]%mod;for(int j=2*i;j<=1000000;j+=i)cnt[i]+=cnt[j];}for(int i=1000000;i>=2;i--){if(cnt[i])dp[i]=1ll*cnt[i]*f[cnt[i]-1]%mod;for(int j=2*i;j<=1000000;j+=i)dp[i]-=dp[j],dp[i]=(dp[i]+mod)%mod;ans+=1ll*i*dp[i]%mod;}printf("%I64dn",ans%mod);}

 

          CodeForce1043F 隐晦的因子容斥，需要注意到答案t在1~8之间 维护dp[j]：n个数取t个数gcd为j的方案数 //CF1043F题意：n个数选尽量少的数使得gcd为1 n，ai<=3e5 如果没有输出-1 //思路：//首先，如果答案存在，那么最多为7(因为前7个质数乘起来>=3e5)//问题转化成n个数取i个数gcd为1的方案数不为0 的最小的i //考虑DP[i][j] n个数选i个数gcd为j的方案数 //子集选取gcd为j,考虑因子容斥 //dp[i][j]-=dp[i][j*k] ,k>=2 初始dp[i][j]=C(cnt[j],i);//问题变成找到最小的i使得dp[i][1]>0//i从小到大枚举检测即可 #include<bits/stdc++.h>#define ll long longusing namespace std;const int mod=1e9+7; int a[300005];ll dp[10][300005];int cnt[300005];int jc[300005];int jv[300005];ll qmod(ll a,ll b){ll res=1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b=b>>1;}return res;} ll getC(ll a,ll b){if(a<b)return 0;return 1ll*jc[a]*jv[b]%mod*jv[a-b]%mod;}int main(){jc[0]=jv[0]=1;for(int i=1;i<=300000;i++)jc[i]=1ll*jc[i-1]*i%mod,cnt[i]=0;jv[300000]=qmod(jc[300000],mod-2);for(int i=299999;i>=1;i--)jv[i]=1ll*jv[i+1]*(i+1)%mod;int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]),cnt[a[i]]++;for(int i=1;i<=300000;i++){for(int j=2*i;j<=300000;j+=i)cnt[i]+=cnt[j];}for(int i=1;i<=8;i++){for(int j=300000;j>=1;j--){dp[i][j]=getC(cnt[j],i);for(int k=2*j;k<=300000;k+=j)dp[i][j]=(dp[i][j]-dp[i][k]+mod)%mod;}if(dp[i][1]>0){printf("%dn",i);return 0;}}//5 7 2 4 4 4//printf("test:%d %d %d %dn",dp[2][1],dp[2][2],dp[2][4],dp[2][8]); puts("-1");}   CodeForce803F 经典的因子容斥 //CF803F 因子容斥 n<=1e5,ai<=1e5 //题意：问有多少个子集S满足gcd(S)==1 //思路：设dp[j]为 子集的gcd恰好是j的个数//现在求 dp[1] //cnt[j]表示有多少个ak满足ak是j的倍数//在cnt[j]里取任意个都是满足要求的子集 //C(cnt[j],1)+C(cnt[j],2)+... C(cnt[j],cnt[j]) =2^cnt[j]-1//初始化dp[j]=2^cnt[j]-1,此时dp[j]表示子集的gcd是j的倍数的个数//我们要求恰好为j的个数，因子容斥即可 //一开始想设dp[i][j]为n个选i个gcd为j的方案数//但是Wa13了才发现i可以取很大#include<bits/stdc++.h>#define ll long longusing namespace std;const int mod=1e9+7;int cnt[100005];int a[100005];ll dp[100005];ll jc[100005];ll jv[100005];//ll getc(ll a,ll b)//{//if(a<b)return 0;//return 1ll*jc[a]*jv[b]%mod*jv[a-b]%mod;//}ll qmod(ll a,ll b){ll res=1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b=b>>1;}return res;}int main(){//jc[0]=jv[0]=1;//for(int i=1;i<=100000;i++)jc[i]=jc[i-1]*i%mod;//jv[100000]=qmod(jc[100000],mod-2);//for(int i=99999;i>=1;i--)jv[i]=jv[i+1]*(i+1)%mod;int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]),cnt[a[i]]++;for(int i=1;i<=100000;i++){for(int j=2*i;j<=100000;j+=i)cnt[i]+=cnt[j];}ll ans=0;//for(int i=1;i<=60;i++)//{//for(int j=100000;j>=1;j--)//{//dp[i][j]=getc(cnt[j],i);//for(int k=2*j;k<=100000;k+=j)//dp[i][j]=(dp[i][j]-dp[i][k]+mod)%mod;//}//ans=(ans+dp[i][1])%mod;//}for(int j=100000;j>=1;j--){dp[j]=(qmod(2,cnt[j])-1+mod)%mod;for(int k=2*j;k<=100000;k+=j){dp[j]=(dp[j]-dp[k]+mod)%mod;}}ans=(ans+dp[1])%mod;printf("%I64dn",ans%mod);}