| by XianKa | No comments

【2017四川省赛/牛客】2017 Revenge【数论/指标】

传送门

题意是说给2e6个数,每个数都小于2017,从中选取一些数字使得乘积模2017等于给定的r,问方案数%2输出

DP,f[i][ja[i]%2017]=f[i-1][j]+f[i-1][ja[i]],因为答案只需要奇偶,所以考虑异或操作。

不过这样的复杂度是2017n的。

考虑把乘法变成加法,5是2017的原根,并且2017是质数,剩余系是完全剩余系。所以把1-2016的指标存下来到I[]里面。

f[i][j+I[a[i]]]=f[i-1][j]+f[i-1][j+I[a[i]]]

可以把f开成一个bitset,f[i]表示第i个指标的方案数。所有的状态j每次加一个数I,就相当于循环左移了I位。再用异或滚动状态就可以了。

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

#include<bits/stdc++.h>
using namespace std;
bitset<2016> f;
int a[2000002], I[2020];
int main()
{
    int n, r;
    int g = 1;
    for(int i = 1; i <= 2016; i++) 
    {
        g = g * 5 % 2017;
        I[g] = i;
    }
    // I[1] = 0;
    while(~scanf("%d%d", &n, &r))
    {
        f.reset();
        for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
        f.set(0);
        for(int i = 1; i <= n; i++)
        {
            f ^= (f << I[a[i]]) ^ (f >> (2016 - I[a[i]]));
        }
        cout << f[I[r] % 2016] << endl;
    }
}

发表评论