Bobo has n integers a1,a2,…,ana_1, a_2, \dots, a_n
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.

链接🔗

「2017 四川省赛」2017 Revenge

题解

首先能想到一个2017 * 1e6 的DP
因为答案%2的原因，我们考虑用bitset进行状压优化
但是乘法不方便进行状态方程的转移
我们发现模数2017是存在原根55的
因此我们可以将每个数aia_i映射到 kk,表示ai=5ka_i = 5^k
然后转移的时候，就可以将乘法转化为加法操作

代码

#include <cstdio>
#include <iostream>
#include <bitset>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxd = 2100;
int I[maxd],n,m; // I[i]表示i第个数是5的I[i]次方
void init()
{
    int now = 1;
    for(int i=0;i<2016;i++) I[now] = i,now = 5*now%2017;
}
bitset<2016> dp;
int main()
{
    // freopen("a.in","r",stdin);
    // freopen("k.out","w" ,stdout);
    init();
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        dp.reset();
        dp.set(0);
        for(int i=1;i<=n;i++)
        {
            int x;scanf("%d",&x); x = I[x];
            //dp[i+1][j] = dp[i][j] + dp[i][(j+x)%2017]
            dp^=(dp<<x)|(dp >> (2016 - x));
        }
        printf("%d\n",(int)dp[I[m]]);
    }
    return 0;
}