icontofig | 发布于 2019-10-05 21:34:07 | 阅读量 335 | DP bitset 数论
发布于 2019-10-05 21:34:07 | DP bitset 数论

题目大意

给出n个数,要你从中选出一些数,使得他们的乘积mod 2017的余数为r,问总方案数mod 2的值。

题解

对于一些数的乘法,我们可以用log把他转化乘加法。

但是是在模意义下,就是需要离散模对数了。

这时候我们要求2017的原根,2017的原根是5,我们就可以自然而然的把原来的所有数都化为他们的离散模对数了。

首先如果数据范围很小,我们该怎么写呢?

那么我们可以用dp[i][j]表示当前为第枚举到第i个数,选出的前面的(包括i)所有数的乘积的离散模对数为j的方案数。

那么dp方程就很容易能够想到了:

dp[i][j] = dp[i-1][j] + (dp[i-1][(j-lg[a[i]])%2016]);

这两项分别代表当前项选/不选的情况。

可以看到第i位的值只跟他的前一位有关,所以空间可以滚动掉一维。

但是这样的时间仍然是O(n*2016),n的数据范围让我们无法直接这样去做dp(而且由于依赖性无法使用多线程,这里我又在说胡话了)。

那我们该怎么办?

我们注意一下,答案只需要输出总方案数mod 2的值,所以注意一下dp方程,我们就可以这样去改了:

dp[i][j] = dp[i-1][j] ^ (dp[i-1][(j-lg[a[i]])%2016]);(二进制中的异或运算实际上就是加法对2取模)

也就是dp[j] = dp[j] ^ dp[(j-lg[a[i]])%2016];

计算机系统在进行二进制运算的时候是非常快的,所以可以用二进制的一些东西来加速这个运算,让枚举2016次的复杂度降低成为一个更小的常数,但是通常的数据类型不支持我们这么做。

这时候我们可以用C++中的bitset来对上面的式子进行加速。

如果我们用一个2016位的bitset<2016>f,那么上面的递推式就要写成以下形式:

f ^= (f<<lg[a[i]]) ^ (f>>(2016-lg[a[i]]));

这样由于计算机系统在对于bitset运算的速度较快,我们就可以通过此题了。

注意一定要用cout输出,printf输出会有问题。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
int lg[2020],a[2000005],n,r;
bitset<2016>f;
int main(){
    int p = 1;
    for(int i = 1;i < 2017;++i){
        p = p * 5 % 2017;
        lg[p] = i;
    }
    lg[1] = 0;
    while(scanf("%d%d",&n,&r) != EOF){
        for(int i = 1;i <= n;++i){
            scanf("%d",&a[i]);
        }
        f.reset();
        f.set(lg[1]);
        for(int i = 1;i <= n;++i){
            f ^= (f<<lg[a[i]]) ^ (f>>(2016-lg[a[i]]));
        }
        cout << f[lg[r]] << endl;
    }
    return 0;
}



内容更新于: 2019-10-05 22:22:13
链接地址: http://blog.leanote.com/post/icontofig/%E7%89%9B%E5%AE%A2%E5%9B%BD%E5%BA%86huan-le-sai

上一篇: 牛客欢乐赛4 2017湘潭市赛 C.Intersection 线性基 + 秩(线性代数题目)

下一篇: luogu P3321 BZOJ 3992 [SDOI2015]序列统计 NTT + 生成函数 + 快速幂

335 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航