時間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 32768K，其他語言65536K
Special Judge, 64bit IO Format: %lld
題目描述
Bobo has n integers a1,a2,…,ana_1, a_2, \dots, a_na1,a2,…,an.
He would like to choose some of the integers and calculate their product (the product of the empty set is defined as 1).
Bobo would like to know the number of products whose remainder divided by 2017 is r. As the exact number is too large, he only asks for the number modulo 2.
輸入描述:
The input contains zero or more test cases and is terminated by end-of-file. For each case,
The first line contains two integers n, r.
The second line contains n integers a1,a2,…,ana_1, a_2, \dots, a_na1,a2,…,an.
* 1≤n≤2×1061 \leq n \leq 2\times 10^61≤n≤2×106
* 1≤r,a1,a2,…,an<20171 \leq r, a_1, a_2, \dots, a_n < 20171≤r,a1,a2,…,an<2017
* The sum of n does not exceed 2×1062 \times 10^62×106. 輸出描述:
For each case, output an integer which denotes the parity. 示例1
輸入
3 6
2 3 4
4 1
1 1 2016 2016 輸出
1
0 本題需要用到數論中原根的知識再結合bitset來優化dp。
首先由題意可以想到一個裸的dp， dp(i,j)表示前i個數，選出來的乘積模2017為j的方案數，轉移方程為
，初始狀态為dp[0][1]=1。然而總狀态數為大約2e9，顯然會T。
因為隻需要求方案數模2，或許我們可以聯想到位運算異或，如果能将一層轉移（i相同的轉移）轉化為常數次bitset的操作，計算規模就能降到
，即可通過本題。
要想隻通過常數次bitset操作轉移，那麼我們希望轉移是連續的，比如從[l,r]轉移到[x,y]，其中r-l+1==y-x+1，即區間長度相同，且大小關系也一一對應，對于這樣的區間隻需要一次bitset操作即可完成轉移。
2017是一個奇素數，原根必存在。對于一個奇素數p，模p的原根可以在指數取[1,p-1]區間時，模p得到[1,p-1]的所有值。
模2017有原根5，那麼我們可以用
來表示模2017為x的數，那麼乘法
就可以轉化為指數上的加法
，則我們可以通過映射，使得轉移是連續的。
令dp(i,j)表示前i個數，選出來的乘積為
的方案數，轉移方程為
通過滾動數組，隻需要一個bitset即可完成轉移，有dp=dp^(dp<<I[a[i]])^(dp>>(2016-I[a[i]]))
AC代碼：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2e6+5;
int n,r,I[2017],a[maxn];//5^I[i]%2017 equal i, 5 is 2017's 原根
bitset<2016> dp;//5^[0,2015]%2017 equal [1,2016]%2017
int main(){
//freopen("in.txt","r",stdin);
int tt=1;
for(int i=0;i<2016;i++){
I[tt]=i;
tt=tt*5%2017;
}
while(~scanf("%d %d",&n,&r)){
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
dp.reset();
dp.set(0);//no number was selected
for(int i=1;i<=n;i++){//轉移有兩種：dp[i][j]=dp[i-1][j]+dp[i-1][j-I[a[i]]],後者又可拆為[0,2015-I[a[i]]]轉移到[I[a[i]],2015],[2016-I[a[i]],2015]轉移到[0,I[a[i]]]
dp^=(dp<<I[a[i]])^(dp>>(2016-I[a[i]]));
}
cout<<dp[I[r]]<<"\n";
}
return 0;
}