【BZOJ】4903: [Ctsc2017]吉夫特-DP

題解

盧卡斯定理：

(nm)≡(⌊np⌋⌊mp⌋)(n%pm%p)(modp) ( n m ) ≡ ( ⌊ n p ⌋ ⌊ m p ⌋ ) ( n % p m % p ) ( mod p )

很好證明的。

如何保證 (nm) mod 2 =1 ( n m )   m o d   2   = 1 呢？

結合盧卡斯定理可以發現：

當n&m=m時，上式成立。

我們可以這樣暴力枚舉：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<iostream>
#include<ctime>
#include<cstdlib>
using namespace std;
const int N=,mod=+;

int n,a[N],dp[N],sum;

inline int rd()
{
    char ch=getchar();int x=,f=;
    while(!isdigit(ch)){if(ch=='-') f=-;ch=getchar();}
    while(isdigit(ch)){x=x*+(ch^);ch=getchar();}
    return x*f;
}

int main(){
    int i,j;
    n=rd();
    if(n>){return ;}
   for(i=;i<=n;++i) a[i]=rd(),dp[i]=;
    for(i=;i<=n;++i){
        for(j=;j<i;++j){
            if((a[i]&a[j]) == a[i])
             (dp[i]+=dp[j])%=mod;
        }
        (sum+=dp[i]-)%=mod;
    }
    printf("%d\n",sum);
}
           

我們就可以得70分了！

還需要優化一下：

我們可以枚舉每個數的子集，看枚舉到的數是否存在且下标小于目前數的下标，然後加上就好了。

但是對于下标保證單增就很妙了，

我們可以邊讀入邊枚舉目前數，加給後面的，這樣就不用考慮下标問題了，因為若後面的數枚舉到了前面的數，但答案在前面已經加過了這個數，是以即使更新了前面的數的dp數組，也不會對答案産生影響了。

AC代碼：

#include<cstdio>
using namespace std;
const int N=+,mod=+;
int n,pos[N],sum,now,f[N];

inline void mo(int &x){x-= x>=mod? mod:;}
int main(){
    int i,j;
    scanf("%d",&n);
    for(i=;i<=n;++i){
        scanf("%d",&now);f[now]++;
        for(j=(now-)&now;j;j=(j-)&now)
             mo(f[j]+=f[now]);
        mo(sum+=f[now]-);
    }
    printf("%d\n",sum);
}