2
26
2017
3

BZOJ4762

颓得一匹就来写一下这个题的题解。

鸣谢埃及小哥Ninjo

为了方便转换成所有数的or和为全集。

很容易想到DP,$dp_{i,j,k}$表示做到第i个数,前面的or和为j,后面的or和我们希望它是k的情况。但是直接DP的话复杂度太大了接受不了,所以我们把它子集差分一下,$ans_{i,j,k}=\sum_{l\epsilon k}dp_{i,j,l}$

然后就好了。

$dp_{i,j,k}->dp_{i+1,j,k}$

$dp_{i,j,k}->dp_{i+1,j,k \ and \ (not \ a[i])}$

还有一个不知道为什么TEX萎掉了,看代码吧

简单的容斥

#include<cstdio>
#define Rin register int
#define mo 1000000007
using namespace std;
inline int read(){
    int ret=0;char c=getchar();
    while((c<'0')||(c>'9'))c=getchar();
    while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
    return ret;
}
int dp[2][1024][1024];
int n,test;
int main(){
    n=read();
    dp[0][0][0]=1;
    for(Rin i=0;i<n;i++){
        Rin x=1023-read();
        for(Rin j=0;j<1024;j++)
            for(Rin k=j;;(--k)&=j){dp[i&1^1][j][k]=0;if(k==0)break;}
        for(Rin j=0;j<1024;j++)
            for(Rin k=j;;(--k)&=j){
                if(dp[i&1][j][k]){
                    dp[i&1^1][j][k]=(dp[i&1^1][j][k]+dp[i&1][j][k])%mo;
                    if((x&j)!=x){
                        dp[i&1^1][j|x][k^(k&x)]=(dp[i&1^1][j|x][k^(k&x)]+dp[i&1][j][k])%mo;
                        dp[i&1^1][j|x][(k^(k&x))|(x^(x&j))]=(dp[i&1^1][j|x][(k^(k&x))|(x^(x&j))]-dp[i&1][j][k])%mo;
                    }
                }
                if(!k)break;
            }
    }
    if(dp[n&1][1023][0]<0)dp[n&1][1023][0]+=mo;
    printf("%d",dp[n&1][1023][0]);
}

鼓哥帅啊

Category: flag | Tags: DP bzoj 容斥 | Read Count: 1724
Avatar_small
JDC Result jessore 说:
2022年8月28日 15:29

Jessore Divisional education board of Bangladesh has successfully conducted the Grade 8th terminal examination tests for both Junior School Certificate & Junior Dakhil Certificate course students at all districts under the division to the academic year of 2022, there are a huge number of students are appeared from all Secondary schools under the board like as previous years, JDC Result jessore and this is most important examination tests for class 8th standard students of the country.Government of Bangladesh, Secondary and Higher Secondary Education Board has successfully completed the JSC & JDC examinations in the month of November 2022 to all eligible students of the division at all selected examination centers at all rural and urban area schools, both of Junior School Certificate & Junior Dakhil Certificate terminal exams are conducted as per date sheet announced by all education board Bangladesh.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com