CF1610 D. Not Quite Lee

传送门

题意:给出n个正数a[i..n],a[i]意为长为a[i]的一段任意连续的数,记作b.如a[i]=5,b可以等于[1,2,3,4,5],[-1,0,1,2,3,4],等等.现要求从中选取一个子序列,使得它们对应的b数组所有元素之和可以为0.问一共有几种选法,答案模1e9+7.

解:先分析选取两个数时的情况.易得一奇一偶,两个奇数可以选出b数组使得元素和为零.偶数似乎只有两个数相同时可以.而这两种情况无论再加一个奇数还是偶数也都能成立.故当子序列中有一个奇数时,这种选法恒可行.

现在来分析序列中全是偶数的情况.假设b数组第一个元素为1,则b数组元素和为(1+a[i])*a[i]/2.将其移动,b数组可能的和为x*a[i]+(1+a[i])*a[i]/2=(x+a[i])*a[i]+a[i]/2=m*a[i]+a[i]/2.现在要使∑(a[i]*mi+a[i]/2)=0,即∑(a[i]*mi)=∑(a[i]/2)有解,即gcd(a[1]..a[n])|∑(a[i]/2).证明可由裴蜀定理推得.

裴蜀定理:令d=gcd(a,b),ax+by=m有解当且仅当d|m时成立.

把多个方程加在一起就可以了.

然而到这里枚举的数量还是太大.考虑将上式变形.令d=gcd(a[1]..a[n])移项,2d|∑a[i],左右两边同除d得2|∑(a[i]/d).记a[i]/d为t[i],t[i]一定是整数,且要使2|∑t[i]成立,t[1..n]中不能有奇数个奇数.

现在看来求不行的选法简单一点,也就是求在t[i]中选奇数个奇数的选法.注意选的子序列不同时gcd是会变的,因此不能直接处理整个a数组的gcd然后排列组合.考虑一个数中2作为因子的个数.当这些2被除干净时,它自然就是奇数了.我们不关心这些数原本是几,只关心它除完gcd后的奇偶性,因此考虑预处理所有数中有几个2,并记录下有i个2的数个数为b[i],当它们是子序列中含2最少的元素时,它们除完gcd就会是奇数.

然后就是排列组合题了.先从t[i]个数里选奇数个数,再从后面的数里考虑选与不选,也就是:∑C(2k+1,t[i])*2^t[i+1...].已知∑C(2k+1,t[i])=2^t[i]-1,好了现在可以让电脑算了.最后记得拿所有情况去减掉它.

注:代码中a[i]为上述t[i].

这题我自己想必然想不到后半段,以及今天为什么打不出小圆圈句号哦whyyyyyy

代码:

 1 #include
 2 #include 
 3 #include 
 4 #include 
 5 using namespace std;
 6 #define ll long long
 7 #define maxx 200005
 8 #define inf 0x3f
 9 const int mod=1e9+7;
10 //#define int long long
11 int a[40]={0};
12 ll ksm(ll x,ll y){
13     if(y==1)
14         return x;
15     ll ret=1,base=x;
16     while(y){
17         if(y&1) ret=(ret*base)%mod;
18         base=(base*base)%mod;
19         y>>=1;
20     }
21     return ret;
22 }
23 signed main() {
24     int n;
25     scanf("%d",&n);
26     for(int i=1;i<=n;i++){
27         int t;
28         scanf("%d",&t);
29         int cnt=0;
30         while(t%2==0){
31             cnt++;
32             t/=2;
33         }
34         a[cnt]++;
35     }
36     ll ans=0;
37     for(int i=1;i<32;i++){
38         if(a[i]==0)
39             continue;
40         ll temp=ksm(2,a[i]-1)%mod;
41         for(int j=i+1;j<32;j++)
42             temp=(temp*ksm(2,a[j]))%mod;
43         ans=(ans+temp)%mod;
44     }
45     ans=(ksm(2,n)-1-ans+mod)%mod;
46     printf("%lld\n",ans);
47     return 0;
48 }