【BZOJ 4347】[POI2016] Nim z utrudnieniem

Qizy 动态规划, 杂项, 解题报告

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4347
神犇题解Ⅰ：http://www.cnblogs.com/clrs97/p/5006924.html
神犇题解Ⅱ：http://blog.csdn.net/lych_cys/article/details/50788730

解题报告

这题暴力$DP$的复杂度是$O(nd \cdot \max \{a_i\})$的，显然不能通过此题
但我们注意到，对于一个数$a_i$来讲，小于等于它的数的NIM和不会超过$2 \cdot a_i$
于是我们将$a_i$排序之后再$DP$，每一次枚举异或值只枚举到$2 \cdot a_i$
又因为$\sum\limits_{i=1}^n{a_i} \le 10^7$ 所以公共的更新次数不会超过$2 \cdot 10^7$
于是总时间复杂度就是$O(md)$的了

虽然$md$可以到$10^8$，而且感觉这个上界非常紧的样子
给人一种严重的跑不过的感觉
但却跑得飞快？ 可能是数据比较水吧？

哦，对了，这题还卡内存
连滚动数组都给卡掉了
于是我们学习Claris的技巧，$f[k][j]$和$f[k \ xor \ a_i][j]$一起更新就可以啦！

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int M = 500009;
const int N = 1100000;
const int MOD = 1000000007;
 
int n,D,XOR,f[N][10],g[2][10],arr[M];
 
inline int read() {
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret * f;
}
 
int main() {
    n = read(); D = read(); 
    for (int i=1;i<=n;i++) XOR ^= (arr[i] = read());
    sort(arr+1, arr+1+n); 
    f[0][0] = 1;
    for (int i=1,LIM=1;i<=n;i++) {
        while (LIM <= arr[i]) LIM <<= 1;
        for (int v=1,nv;v<LIM;v++) {
            if ((nv=(arr[i]^v)) <= v) { 
                for (int d=0,t=1%D;d<D;++d,(++t)%=D) {
                    g[1][t] = (f[nv][t] + f[v][d]) % MOD;       
                    g[0][t] = (f[nv][d] + f[v][t]) % MOD;
                }
                for (int d=0;d<D;d++) {
                    f[nv][d] = g[1][d];
                    f[v][d] = g[0][d];
                }
            }
        } 
    }
    if (n % D == 0) f[XOR][0]--;
    printf("%d\n",(f[XOR][0]+MOD)%MOD);
    return 0;
}

16 thoughts to “【BZOJ 4347】[POI2016] Nim z utrudnieniem”

  1. you’re actually a excellent webmaster. The web site loading pace is amazing. It sort of feels that you’re doing any unique trick. Furthermore, The contents are masterwork. you’ve performed a wonderful task in this topic!

    Reply

  2. Its like you read my mind! You appear to know a lot about this, like you wrote the book in it or something. I think that you can do with some pics to drive the message home a little bit, but other than that, this is wonderful blog. An excellent read. I will definitely be back.

    Reply

  5. 723879 503857Hey! Do you know if they make any plugins to protect against hackers? Im kinda paranoid about losing everything Ive worked hard on. Any recommendations? 120643

    Reply

  9. 238274 627328Hey there! Someone in my Myspace group shared this internet site with us so I came to take a look. Im surely enjoying the details. Im bookmarking and will be tweeting this to my followers! Exceptional weblog and outstanding style and design. 954682

    Reply

  16. 132878 2273101 can undertake all sorts of advised excursions with assorted limousine functions. Various offer wonderful courses and numerous can take clients for just about any ride your bike more than the investment banking area, or even for a vacation to new york. ??????? 958132

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *