题解 P3773 【[CTSC2017]吉夫特】

· · 题解

安利blog

传送门

我好菜啊连卢卡斯都不会了QAQ

卢卡斯搞那一坨组合数：

C_{a_i}^{a_j}\equiv C_{a_i/2}^{a_j/2}\times C_{a_i\%2}^{a_j\%2}\pmod 2

后面那个C_{a_i\%2}^{a_j\%2}有四种情况C_0^0,C_0^1,C_1^0,C_1^1，其中只有C_0^1=0。

然后继续处理C_{a_i/2}^{a_j/2}。

我们发现，这不就是把a_i和a_j按二进制拆位了。其中只要出现过C_0^1，C_{a_i}^{a_j}就为0。

也就是说二进制下不存在某一位a_i为0而a_j为1，即a_j二进制下是a_i的子集。

问题就变成了求子序列的个数，满足每一项在二进制下是前一项的子集。

而且都是它的子集了，就不用考虑序列的单调性了。 复杂度就是枚举子集的$O(3^{\log_2\max\{a_i\}})

非常简短的代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define maxn 250005
#define inf 0x3f3f3f3f

const int mod = 1e9 + 7;

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
int f[maxn];
int main(){
    int n=read(),a,ans=0;
    for(register int i=1;i<=n;++i){
        a=read();
        for(register int S=a-1&a;S;S=S-1&a)(f[S]+=f[a]+1)%=mod;
        (ans+=f[a])%=mod;
    }
    printf("%d\n",ans);
}