codeforces 449D Jzzhu and Numbers 배제 + 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;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[BOJ]11048(python)

python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

codeforces 449D Jzzhu and Numbers 배제 + DP

좋은 웹페이지 즐겨찾기