【SRM20】数学场
第一题
n个m位二进制,求异或值域总和。
【题解】异或值域--->使用线性基,解决去重问题。
m位二进制--->拆位,每位根据01数量可以用组合数快速统计总和。
#include<cstdio> #include<cstring> #include<cctype> #include<cmath> #include<bitset> #include<algorithm> #define ll long long using namespace std; int read(){ char c;int s=0,t=1; while(!isdigit(c=getchar()))if(c=='-')t=-1; do{s=s*10+c-'0';}while(isdigit(c=getchar())); return s*t; } /*------------------------------------------------------------*/ const int inf=0x3f3f3f3f,maxn=410,MOD=1e9+7; int n,m,fac[maxn],fav[maxn],f2[maxn],sum,ans; char s[maxn]; bitset<maxn>a[maxn],b[maxn]; void gcd(int a,int b,int &x,int &y){ if(!b){x=1;y=0;} else{gcd(b,a%b,y,x);y-=x*(a/b);} } int inv(int a){ int x,y; gcd(a,MOD,x,y); return ((x%MOD)+MOD)%MOD; } int C(int n,int m){return 1ll*fac[n]*fav[m]%MOD*fav[n-m]%MOD;} int main(){ n=read();m=read(); for(int i=1;i<=n;i++){ scanf("%s",s+1); for(int j=1;j<=m;j++)a[i][m-j]=s[j]-'0'; for(int j=m-1;j>=0;j--)if(a[i][j]){ if(b[j]==0){b[j]=a[i];break;} else a[i]^=b[j]; } } int sum0,sum1; fac[0]=1;for(int i=1;i<=m;i++)fac[i]=1ll*fac[i-1]*i%MOD; for(int i=0;i<=m;i++)fav[i]=inv(fac[i]); f2[0]=1;for(int i=1;i<=m;i++)f2[i]=1ll*f2[i-1]*2%MOD; ans=0; for(int i=0;i<m;i++){ sum0=sum1=sum=0; for(int j=0;j<m;j++)if(b[j]!=0){ if(b[j][i]==0)sum0++;else sum1++; for(int j=1;j<=sum1;j+=2)sum=(sum+C(sum1,j))%MOD; ans=(ans+1ll*f2[i]*sum%MOD*f2[sum0]%MOD)%MOD; } printf("%d",ans); return 0; }
第二题
给定n个数,求从中任意选数的所有方案gcd的总和。n个数字都<=m(给定)。n<=10^5,m<=10^6。
【题解】对于每个数字a(1<=a<=m)处理出n个数中有多少个是它的倍数,记为b,那么有它是2^b-1种方案的公因数,再容斥掉其倍数(ans[j])得到ans[i]。
使用的仍是自带容斥的技巧,就是直接容斥掉已经计算过的答案ans,这些答案ans已经自带上一层容斥了。
复杂度分析:1枚举n次,2枚举n/2次,所以总共枚举n*(1+1/2+1/3+1/4+...+1/n),后面的数列是常见的近似ln(n),所以总复杂度O(n ln n)。
#include<cstdio> #include<algorithm> using namespace std; const int maxn=1000010,MOD=1e9+7; int n,m,f2[maxn],a[maxn],b[maxn],ans[maxn],ANS=0; int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[a[i]]++; f2[0]=1;for(int i=1;i<=m;i++)f2[i]=f2[i-1]*2%MOD; for(int i=m;i>=1;i--){ int num=0; for(int j=i;j<=m;j+=i)num+=b[j]; ans[i]=f2[num]-1; for(int j=i+i;j<=m;j+=i)ans[i]=(ans[i]+MOD-ans[j])%MOD; ANS=(ANS+1ll*i*ans[i]%MOD)%MOD; } printf("%d",ANS); return 0; }