落谷3773 数论+dp递推

布满荆棘的人生 2022-05-14 08:39 113阅读 0赞

[https://www.luogu.org/problemnew/show/P3773][https_www.luogu.org_problemnew_show_P3773]

这个题就用到了上篇博客[https://blog.csdn.net/du\_lun/article/details/82414086][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;
    }

[https_www.luogu.org_problemnew_show_P3773]: https://www.luogu.org/problemnew/show/P3773
[https_blog.csdn.net_du_lun_article_details_82414086]: https://blog.csdn.net/du_lun/article/details/82414086