P2490 [SDOI2011]黑白棋
P2490 [SDOI2011]黑白棋
题意
一个 \(1*n\) 的棋盘上,A 可以移动白色棋子,B 可以移动黑色的棋子,其中白色不能往左,黑色不能往右。他们每次操作可以移动 1 到 \(d\) 个棋子。
每当移动某一个棋子时,这个棋子不能跨越两边的棋子,当然也不可以出界。当谁不可以操作时,谁就失败了。
思路
显然可以将题意转化为一种 K-Nim 游戏,即在 \(\frac k2\) 堆石子中,每次可将 \(d\) 堆石子取任意个,令对手无路可走时获胜。
用总方案数减去先手必败的方案数即为答案,因为先手必败方案更加好算。
K-Nim 游戏
结论
设 \(r_i\) 为二进制第 \(i\) 位所有数该位为 1 的个数 \(\pmod {d+1}\) 的值,那么只用一步即可在 “\(r\) 全为 0” 和 “\(r\) 不全为 0” 两种状态间转移。
感性证明
考虑一个大小不超过 \(d\) 的集合,为我们一次操作需要拿走的石子堆的集合,选 0 或 1 都是合法的。
假设我们现在已经有这样一个大小为 \(d\) 的集合,其中有 \(x\) 个 1,\(y\) 个 0,即 \(x+y=d\)。我们要让 \(r\) 等于零,分以下情况:
- \(x\ge r\) 则选择 \(r\) 个 1 变为 0 即可。
- \(x<r\) 则 \(y+r\ge d+1\) ,则选择 \(d-r+1\) 个 0 变为 1 即可。
所以一定有一种方法使这一位的 \(r\) 变成 0.
现在我们并没有一个可以随便转换的集合,但是当一个数的高位从 1 变为 0 之后低位就可以随便选 0 和 1.所以我们从高位向低位考虑,如果一直符合第二个情况就向下考虑,否则就是第一个情况,并且在这种情况下把 1 变成 0 是合法的,那么我们扩大集合即可。
得证。
在上述博弈中,所有 \(r\) 为 0 的状态是必败态。我们只需要算所有这种情况的方案就可以了。
考虑 Dp。设 \(f_{ij}\) 为前 \(i\) 位的 \(r\) 均为 0,总共 \(j\) 个石子的方案数。
新选一位,枚举在 \(d+1\) 堆石子中放入若干次石子。即
\]
最后统计答案需要枚举每一堆的起点位置,即在原题中的白棋的位置,答案为所有位的
\]
的和。
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<cmath>
using namespace std;
inline int read(){
int w=0,x=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c))x=x*10+(c^48),c=getchar();
return w?-x:x;
}
namespace star
{
const int maxn=10005,mod=1e9+7;
int n,k,d,C[maxn][205],f[18][100005];
inline void work(){
n=read(),k=read(),d=read();
C[0][0]=1;
for(int i=1;i<=n;i++){
C[i][0]=1;
for(int j=1;j<=200;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
f[0][0]=1;
for(int i=0;i<=16;i++) for(int j=0;j<=n-k;j++) for(int x=0;(1ll<<i)*x*(d+1)<=n-k and x*(d+1)<=k/2;x++)
f[i+1][j+(1ll<<i)*x*(d+1)]=(f[i+1][j+(1ll<<i)*x*(d+1)]+1ll*f[i][j]*C[k/2][x*(d+1)])%mod;
int ans=0;
for(int i=0;i<=n-k;i++) ans=(ans+1ll*f[17][i]*C[n-i-k/2][k/2])%mod;
printf("%d\n",(C[n][k]-ans+mod)%mod);
}
}
signed main(){
star::work();
return 0;
}
最新文章
- JavaScript中的日期处理注意事项
- linux ssh 登录同时执行其他指令
- Difference between Char.IsDigit() and Char.IsNumber() in C#
- django 命名空间详解
- 使用intellij idea搭建MAVEN+springmvc+mybatis框架
- 第二章——第二节 IPC机制的概述和使用
- Codeforces 474A Keyboard (水
- SpringMVCURL请求到Action的映射规则
- ios NSString拼接方法总结
- Java高并发秒杀API之业务分析与DAO层
- T-SQL基础(一)之简单查询
- ES6标准入门之变量的解构赋值简单解说
- MySql(十七):MySql架构设计——高可用设计之思路及方案
- hadoop学习笔记(六):HBase体系结构和数据模型
- java并发编程实战:第十章----避免活跃性危险
- RESTful作用与特性
- TestNG测试报告美化
- 使用Entity Framework出错
- Group By 和 Having, Where ,Order by执行顺序
- bzoj 4773: 负环 floyd
热门文章
- Appium 工作原理及 Desired Capabilities
- Web打印插件实现思路(C#/Winform)
- 重新整理 .net core 实践篇—————异常中间件[二十]
- 使用allure工具生成测试报告(基于pytest框架)
- 【SQLite】批处理脚本BAT读取SQLite数据
- 想玩转JAVA高并发,这些概念你必须懂
- leetcode5698.基本计算器
- DOS命令行(11)——更多实用的命令行工具
- 关于win10 samba访问提示用户名和密码错误的原因
- 『无为则无心』Python基础 — 12、Python运算符详细介绍