bzoj千题计划247：bzoj4903: [Ctsc2017]吉夫特

http://uoj.ac/problem/300

预备知识：

C（n，m）是奇数的充要条件是 n&m==m

由卢卡斯定理可以推出

选出的任意相邻两个数a，b 的组合数计算C（a，b）必须是奇数

所以可以设dp[i][j] 表示前i个数里面，选的最后一个数是第j个数的方案数

转移的时候，枚举前i-1个数选的最后一个数k，

若C（k，i）是奇数,dp[i][j]+=dp[i-1][k]

时间复杂度：O（n^3）

#include<cstdio>
#include<iostream>

using namespace std;

#define N 20

const int mod=1e9+7;

int a[N];

int dp[N][N];

void read(int &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}

bool judge(int x,int y)
{
    if(!x) return true;
    return (x&y)==y;
}    

int main()
{
    int n;
    read(n);
    for(int i=1;i<=n;++i) read(a[i]);
    dp[0][0]=1;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=i;++j) 
        {
            dp[i][j]=1;
            for(int k=1;k<j;++k)
                if(judge(a[k],a[j])) 
                {
                    dp[i][j]+=dp[i-1][k];
                    dp[i][j]-=dp[i][j]>=mod ? mod : 0;
                }
        }
    int ans=0;
    for(int i=1;i<=n;++i) 
    {
        ans+=dp[n][i]-1;
        ans-=ans>=mod ? mod : 0;
    }
    printf("%d",ans);
}

View Code

#include<cstdio> #include<iostream> using namespace std; #define N 2018 const int mod=1e9+7; int a[N]; int dp[N]; void read(int &x) { x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } } int main() { int n; read(n); for(int i=1;i<=n;++i) read(a[i]); for(int i=1;i<=n;++i) dp[i]=1; for(int i=1;i<=n;++i) { for(int j=1;j<i;++j) if((a[j]&a[i])==a[i]) dp[i]+=dp[j]; } int ans=0; for(int i=1;i<=n;++i) { ans+=dp[i]-1; ans-=ans>=mod ? mod : 0; } printf("%d",ans); }

#include<cstdio> #include<iostream> using namespace std; #define N 233334 const int mod=1e9+7; int a[N]; int dp[N]; int pos[N]; void read(int &x) { x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } } int main() { int n; read(n); for(int i=1;i<=n;++i) read(a[i]),pos[a[i]]=i; int bit,sum; for(int i=1;i<=n;++i) { dp[a[i]]++; for(int j=(a[i]-1)&a[i];j;j=(j-1)&a[i]) if(pos[j]>i) { dp[j]+=dp[a[i]]; dp[j]-=dp[j]>=mod ? mod : 0; } } int ans=0; for(int i=1;i<=n;++i) { ans+=dp[a[i]]-1; ans-=ans>=mod ? mod : 0; } printf("%d",ans); }

#include<cstdio> #include<iostream> using namespace std; #define N 233334 const int mod=1e9+7; int a[N]; int dp[N]; void read(int &x) { x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } } int main() { int n,x; int ans=0; read(n); for(int i=1;i<=n;++i) { read(x); dp[x]++; for(int j=(x-1)&x;j;j=(j-1)&x) { dp[j]+=dp[x]; dp[j]-=dp[j]>=mod ? mod : 0; } ans+=dp[x]-1; ans-=ans>=mod ? mod : 0; } printf("%d",ans); }

bzoj千题计划247：bzoj4903: [Ctsc2017]吉夫特

相关推荐