codeforces 449D Jzzhu and Numbers 배제 + DP

2227 단어 DP
흥미로운 문제는 몇 개의 하위 서열을 찾아서 각 원소의 & 값을 0으로 하는 것이다.
만약 모든 것이 0이라면 방안은 분명히 2^n-1이지만 아마도 많은 편이다.각각 1위부터 20위까지 1이 틀림없는 상황을 고려하면 & 연산이기 때문에 1이 틀림없다.그리고 두 분의, 세 분의...정답은 ∑-1^d(x)*(2^f(x)-1), x의 범위의 [0,1<20), d(x)는 x가 2진법으로 바뀐 수량이 얼마나 되는지, f(x)는 ai&x==x의 숫자 개수를 충족시키는 것을 의미한다.
현재의 문제는 f(x)를 어떻게 계산하는가이다. 직접적인 폭력은 분명 믿을 수 없기 때문에 우리는 dp[i][j]로 어떤 상태를 나타낸다. j는 이진수이다. 우리는 j의 낮은 i위는 x0이고 다른 높은 위치는 x1이다. 즉, x1x0==j, x0의 1은 어떤 수를 나타내는 이 자리가 반드시 1이고 0은 이 수를 나타내는 이 자리가 임의의 수가 될 수 있다는 것을 기억해도 된다.x1에서 1은 이 수를 나타내는 이 자리가 틀림없이 1이고 0은 이 수를 나타내는 이 자리가 틀림없이 0이며 이런 상황을 만족시키는 숫자의 개수를 나타낸다.분명히 dp[19][j]=f(j).우리는 전이 방정식을 쉽게 얻을 수 있다.
//#pragma comment(linker, "/STACK:102400000,102400000")
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define MP(x,y) make_pair((x),(y))
#define PB(x) push_back(x)
typedef long long LL;
//typedef unsigned __int64 ULL;
/* ****************** */
const LL INF=1LL<<60;
const double INFF=1e100;
const double eps=1e-8;
const int mod=1000000007;
const int NN=100005;
const int MM=1000010;
/* ****************** */

int dp[20][1<<20];
int a[1<<20];

int q_pow(int x,int n,LL mod)
{
    LL ans=1,xx=x;
    for(;n>0;n>>=1)
    {
        if(n&1)ans=ans*xx%mod;
        xx=xx*xx%mod;
    }
    return (int)ans;
}

int main()
{
    int n,i,j,mask=1<<20;
    int ans,t,tt;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);

    memset(dp,0,sizeof(dp));
    for(i=1;i<=n;i++)
    {
        if(a[i]&1)
        {
            dp[0][ a[i] ]++;
            dp[0][ a[i]^1 ]++;
        }
        else
        {
            dp[0][ a[i] ]++;
        }
    }
    for(i=0;i<19;i++)
        for(j=0;j=mod)ans-=mod;
        if(ans<0)ans+=mod;
    }

    printf("%d
",ans);

    return 0;
}
클래스를 사용하여 트위터 API 모듈 만들기
hdu 3681 Prison Break(dp || dfs)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage