[POI2016]Nim z utrudnieniem
2024-09-13 01:13:43
Description
A和B两个人玩游戏,一共有m颗石子,A把它们分成了n堆,每堆石子数分别为a[1],a[2],...,a[n],每轮可以选择一堆石子,取掉任意颗石子,但不能不取。谁先不能操作,谁就输了。在游戏开始前,B可以扔掉若干堆石子,但是必须保证扔掉的堆数是d的倍数,且不能扔掉所有石子。A先手,请问B有多少种扔的方式,使得B能够获胜。
Input
第一行包含两个正整数n,d(1<=n<=500000,1<=d<=10)。
第二行包含n个正整数a[1],a[2],...,a[n](1<=a[i]<=1000000)。
本题中m不直接给出,但是保证m<=10000000。
Output
输出一行一个整数,即方案数对10^9+7取模的结果。
Sample Input
5 2
1 3 4 1 2
1 3 4 1 2
Sample Output
2
$f[i][j][k]$表示前i个石堆j为取走的石子堆%d值,k为取走石子的异或值
$f[i][j][k]=f[i-1][j-1][k~xor~a[i]]+f[i-1][j][k]$
复杂度$O(n*maxa*d)$
但可以发现$a[i]$和小于$a[i]$的数异或和不会超过$2*a[i]$
所以按$a$排序,限制$k$的枚举上界
此题卡空间
先把第一维去掉,然后一个一个试数组开多大,因为开到$10*2000000$肯定会超
$f[i][j][k]=f[i-1][j-1][k~xor~a[i]]+f[i-1][j][k]$
复杂度$O(n*maxa*d)$
但可以发现$a[i]$和小于$a[i]$的数异或和不会超过$2*a[i]$
所以按$a$排序,限制$k$的枚举上界
此题卡空间
先把第一维去掉,然后一个一个试数组开多大,因为开到$10*2000000$肯定会超
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int Mod=1e9+;
int f[][],g[],n,d,a[],lim,s;
int main()
{int i,j,k;
scanf("%d%d",&n,&d);
for (i=;i<=n;i++)
{
scanf("%d",&a[i]);
s^=a[i];
}
sort(a+,a+n+);
f[][]=;
for (i=;i<=n;i++)
{
lim=;
while (lim<=a[i]) lim*=;
for (j=;j<lim;j++)
{
g[j]=f[][j]+f[d-][j^a[i]];
if (g[j]>=Mod) g[j]-=Mod;
}
for (j=d-;j;j--)
{
for (k=;k<lim;k++)
{
f[j][k]=f[j-][k^a[i]]+f[j][k];
if (f[j][k]>=Mod) f[j][k]-=Mod;
}
}
for (j=;j<lim;j++)
{
f[][j]=g[j];
}
}
if (n%d==) f[][s]--;
if (f[][s]<) f[][s]+=Mod;
printf("%d\n",f[][s]);
}
最新文章
- web服务器集群
- centos6.7下安装mvn 、安装elasticsearch下ik分词
- [2015.07.27]万峰图片批量处理专家 v8.6
- 网站Session 处理方式
- 设备像素比devicePixelRatio简单介绍
- 高质量c/c++里的strcpy()
- HTML的标签-W3School读后总结
- Java7 新特性 数值文本表示法
- UINavigationController 操作记录
- Asp.net 导入Excel数据
- the assignment of reading paper
- Delphi笔记(GL_Scene四轴飞行器模型)
- form表单中经常用到的禁用获取值问题
- Basic Linux Privilege Escalation
- PKU《程序设计》专项课程_递归汉诺塔问题
- (python)排序算法
- 基于Xshell使用密钥方式连接远程主机
- html css類和css()
- vue之v-if和v-show
- python3.4学习笔记(十一) 列表、数组实例