2019牛客国庆集训派对day5 K 2017 Revenge 【原根】+【bitset优化dp】_happy_windman的博客-程序员秘密_2017的原根

技术标签: 原根  bitset优化dp  数论的学习  

时间限制: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(i,j)=(dp(i-1,\frac{j}{a[i]}\ mod\ 2017)+dp(i-1,j))\ mod\ 2,初始状态为dp[0][1]=1。然而总状态数为大约2e9,显然会T。

因为只需要求方案数模2,或许我们可以联想到位运算异或,如果能将一层转移(i相同的转移)转化为常数次bitset的操作,计算规模就能降到 \frac{2*10^9}{64}=3.125*10^7,即可通过本题。

要想只通过常数次bitset操作转移,那么我们希望转移是连续的,比如从[l,r]转移到[x,y],其中r-l+1==y-x+1,即区间长度相同,且大小关系也一一对应,对于这样的区间只需要一次bitset操作即可完成转移。

2017是一个奇素数,原根必存在。对于一个奇素数p,模p的原根可以在指数取[1,p-1]区间时,模p得到[1,p-1]的所有值。

模2017有原根5,那么我们可以用5^{I[x]}\ mod\ 2017来表示模2017为x的数,那么乘法j*x\ mod\ 2017就可以转化为指数上的加法5^{I[j]+I[x]}\ mod\ 2017,则我们可以通过映射,使得转移是连续的。

令dp(i,j)表示前i个数,选出来的乘积为5^{j}\ mod\ 2017的方案数,转移方程为

dp(i,j)=dp(i-1,j)\ xor\ dp(i-1,j-I[a[i]])\ if \ j\in [I[a[i]],2015]\\ dp(i,j)=dp(i-1,j)\ xor\ dp(i-1,j+2016-I[a[i]])\ if\ j \in [0,I[a[i]]-1]

通过滚动数组,只需要一个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;
}

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_38515845/article/details/102382930

智能推荐

Flume菜鸟(一)--------Flume简介_chulan8183的博客-程序员秘密

本人是只有一年工作经验的Java菜鸟,说不上对Flume有多深的了解,只是由于工作需要,才接触到Flume,博客内容也是自己在学习flume的些许心得,仅供参考,Flume官网既有使用文档,也有开发文档,很齐全,有英语基础的可以直接看官网文档。博客发表时,Flume最新版本为1.7,本文就以1...

Phoenix填坑记1:索引无故被disable_IT源哥的博客-程序员秘密

Phoenix是基于HBase的,而Phoenix的索引其实是HBase的二级索引,当Phoenix的索引处于disable状态时,整个Phoenix表是无法正常使用的,要将索引修复为enable状态,往往需要重建索引,这对应一些大表来说,往往需要花费几个小时是时间,那么这几个小时,系统基本上就处于不可用状态,这对应现网系统来说,往往是不可接受的。 其实Phoenix有3个隐藏参数,这些参数在官网文档没有体现,但实际上这3个参数非常重要,可以解决上面提到的问题。 闲话不说,先来讲...

通过 Vite 的 create-app 学习如何实现一个简易版 CLI_fewuliu的博客-程序员秘密_create-vite-app

前言前段时间,尤雨溪回答了一个广大网友都好奇的一个问题:Vite 会不会取代 Vue CLI?答案是:是的!那么,你开始学 Vite 了吗?用过 Vite 的同学应该都熟悉,创建一个 Vite 的项目模版是通过 npm init @vitejs/app 的方式。而 npm init 命令是在 [email protected] 开始支持的,实际上它是先帮你安装 Vite 的 @vitejs/create-app 包(package),然后再执行 create-app 命令。至于 @vitejs/create-ap

nginx+tomcat+msm集群共享session_weixin_34233679的博客-程序员秘密

为什么80%的码农都做不了架构师?&gt;&gt;&gt; ...

L2-020. 功夫传人_wanghandou的博客-程序员秘密

L2-020. 功夫传人一门武功能否传承久远并被发扬光大,是要看缘分的。一般来说,师傅传授给徒弟的武功总要打个折扣,于是越往后传,弟子们的功夫就越弱…… 直到某一支的某一代突然出现一个天分特别高的弟子(或者是吃到了灵丹、挖到了特别的秘笈),会将功夫的威力一下子放大N倍 —— 我们称这种弟子为“得道者”。这里我们来考察某一位祖师爷门下的徒子徒孙家谱:假设家谱中的每个人只有1位师傅(除

随便推点

浏览器模拟器之Splash的使用_来时春尽的博客-程序员秘密_splash模拟输入

Splash Lua脚本使用方法基本实例:function main(splash, args) assert(splash:go(args.url)) assert(splash:wait(0.5)) return { html = splash:html(), png = splash:png(), har = splash:har(), }end返回值形式:字典形式return {hello=“word!”}返回一个字符串格式return

安装skimage库报错的解决办法_佳hong的博客-程序员秘密_import skimage报错

在代码中,会看到有from skimage.measure.simple_metrics import compare_psnr如果直接运行 pip install skimage会发现安装不上去其实应该安装的是scikit-image,运行pip install scikit-image

图片色彩失真 html,矢量图会失真吗?_己见明的博客-程序员秘密

矢量图,也称为面向对象的图像或绘图图像,在数学上定义为一系列由线连接的点。矢量文件中的图形元素称为对象。每个对象都是一个自成一体的实体,它具有颜色、形状、轮廓、大小和屏幕位置等属性。矢量图不会失真。矢量图是根据几何特性来绘制图形,矢量可以是一个点或一条线,矢量图只能靠软件生成,文件占用内在空间较小,因为这种类型的图像文件包含独立的分离图像,可以自由无限制的重新组合。它的特点是放大后图像不会失真,和...

7-imageProjection_原理分析_loyer_kong的博客-程序员秘密

对于imageProjection的原理分析。对于其中的数学原理进行一次解析,与代码配合使用。

一文详解MySQL权限_JAVA葵花宝典的博客-程序员秘密

 原文:https://www.cnblogs.com/Csir/p/7889953.htmlMySQL权限级别介绍MySQL权限级别全局性的管理权限,作用于整个MySQ...

Visual Studio 2017 编译 Freeglut_zhanxi1992的博客-程序员秘密

FreeGLUT是 OpenGL 官方推荐使用的 GL库,用于替换许久不更新的GLUT库。OpenGL入门学习常用库之一,下面详细介绍如何在 Windows 平台编译 FreeGLUT库。当然你也可以直接去官网下载编译好的库,各平台下载地址:https://www.transmissionzero.co.uk/software/freeglut-devel/freeglut 3...

推荐文章

热门文章

相关标签