【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