落谷3773 數論+dp遞推

https://www.luogu.org/problemnew/show/P3773

這個題就用到了上篇部落格https://blog.csdn.net/du_lun/article/details/82414086，周遊子集的小技巧，

題意是找有多少個長度>=2的下降子序列，滿足mod2的lucas，并且值大于0

由lucas可以知道C(x,y)=C(a1,b1)*C(a2,b2)……由于ai,bi非零即1，是以 隻要出現C(0,1)結果就會是0，

是以在轉移的時候，隻要找到這個數二進制中一的子集代表的數，轉移就好。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int n, a[N];
int dp[N];
bool vis[N];
int p=1e9+7;
int main(){
    int n;
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
        scanf("%d", &a[i]);
    for(int i=n; i>=1; i--){
        int t=a[i];
        int s=t&(t-1);
     
        while(s){
         
            if(vis[s])
                dp[a[i]]=(dp[a[i]]+(dp[s]+1))%p;
            s=t&(s-1);
        }
     
        vis[t]=true;
    }
    
    int ans=0;
    for(int i=1; i<=n; i++)
        ans=(ans+dp[a[i]])%p;

    printf("%d\n", ans);


    return 0;
}
           

第二種方法是看那個數的子集包含自己，正着推

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1000000007;
ll f[233334], n, ans = 0;
int main() {
    scanf("%d", &n);
    int t;
    for(int i=1; i<=n; i++){
        scanf("%d", &t);
        for(int j=t; j<=233333; j=(j+1)|t)
            f[t]=(f[t]+f[j])%mod;
        ans=(ans+f[t])%mod;
        f[t]++;
    }

    printf("%lld\n", ans);
    return 0;
}