传送门

题意是说给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;
    }
}