【DP】BZOJ4347[POI2016]Nim z utrudnieniem

하나의 권한 문제/(예 o 예)/~~ 전송할 수 없습니다
Time Limit: 30 Sec Memory Limit: 64MB Description A와 B 두 사람이 게임을 하는데 모두 m개의 돌이 있다. A는 그것들을 n더미로 나눈다. 한 무더기의 돌 수는 각각 a[1], a[2]이다.a[n], 매 라운드마다 한 무더기의 돌을 선택하여 임의의 돌을 제거할 수 있지만 빼지 않을 수 없습니다.먼저 조작할 수 없는 사람이 진다.게임이 시작되기 전에 B는 약간의 돌무더기를 버릴 수 있지만 반드시 버리는 무더기가 d의 배수이고 모든 돌무더기를 버릴 수 없다는 것을 보증해야 한다.A 선수, B는 몇 가지 던지는 방식이 있어서 B가 이길 수 있는지 물어보세요.Input 첫 번째 줄은 두 개의 정수 n을 포함하고 d(1<=n<=500000, 1<=d<=10) 두 번째 줄은 n개의 정수 a[1], a[2]를 포함한다.a[n] ( 1<=a[i]<=1000000 ). 본 문제에서 m는 직접 제시하지 않지만 m<=10000000을 보증합니다.Output은 109+7 스키마 수를 기준으로 한 행의 정수를 출력합니다.Sample Input 5 2 1 3 4 1 2 Sample Output 2
지식 비축: 이 무더기의 돌의 수가 1이 되면 선수는 반드시 이기고, 그렇지 않으면 선수는 반드시 진다.그래서 이 문제는 d의 배수를 삭제한 돌무더기로 바뀌어 남은 돌의 이치가 0이 되었다.dp[i][j][k]로 하여금 이전 i의 몇몇 더미 k=cnt의 다른 값이나 값을 j로 삭제하면 dp[i+1][j][(k+1)%d]+=dp[i][j^num[i]][k]를 삭제한다.그리고 우리는 a를 정렬한 후에 이동할 때의 유효 상태가 j만큼 크지 않고 최대 2\a[i]에 이르지 않는다는 것을 발견했다.이렇게 다시 스크롤 그룹을 사용하면 시간을 초과하지 않을 것이다.(≧▽≦)/~
그러나 우리가 메모리를 보았을 때 이 카드의 메모리인 QAQ를 발견했다. 다시 생각해 보면 스크롤 그룹을 열 필요가 없고 가방처럼 1차원이 필요하지 않다.그러나 일부 값은 앞당겨 업데이트되고 더 이상 원래의 값이 아니다.그러나 이런 값은 f[k][0]뿐입니다. 다른 그룹으로 저장하면 됩니다.
AC~(≥≤)/~랄랄라 자동 꽃뿌리기(안개

#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAXN 1<<20
#define mod 1000000007
using namespace std;

int n, m, d, f[11][MAXN], sum, temp[MAXN];
int num[500005];

int main()
{
    scanf("%d%d",&n,&d);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&num[i]);
        sum^=num[i];
    }
    sort(num+1,num+n+1);
    f[0][0]=1;
    for(int i=1, bit=1, x;i<=n;++i)
    {
        x=num[i];
        while (bit<=x) bit<<=1;
        for(int k=0;k<bit;++k)
        {
            temp[k]=f[d-1][k^x]+f[0][k];
            if(temp[k]>=mod)temp[k]-=mod;
        }
        for(int j=d-1;j;--j)
            for(int k=0;k<bit;++k)
            {
                f[j][k^x]+=f[j-1][k];
                if(f[j][k^x]>=mod)f[j][k^x]-=mod;
            }
        for(int k=0;k<bit;++k)
            f[0][k]=temp[k];
    }
    int ans=f[0][sum];
    if(n%d==0)
    {
        --ans;
        if(ans<0)ans+=mod;
    }
    printf("%d
",ans);
    return 0;
}