首页 > 其他分享 >[SDOI2019] 移动金币 题解

[SDOI2019] 移动金币 题解

时间:2023-03-06 11:44:42浏览次数:48  
标签:偶数 return int 题解 石子 金币 异或 SDOI2019 mod

首先考虑一个状态什么时候是合法的。不难把游戏过程抽象为阶梯 Nim 博弈。

根据阶梯 Nim 博弈的结论,先手必胜当且仅当奇数位上的异或和不为 0。

考虑将本题中每个棋子后面的若干格子数视作石子数,那么先手必胜的条件就是偶数位上的石子数异或和不为 0(奇数位变为偶数位是因为第一颗棋子前面还有一堆没用的)。

新的题意:\(n-m\) 个石子,分成 \(m+1\) 堆,求偶数位上石子数异或和不为 0 的方案数。

限制很强,考虑容斥,算偶数位上异或和为 0 的方案数,再用 \(\binom{n}{m}\) 减去它即可。

考虑一个 naive 的 DP:设 \(f(i,j,k)\) 表示前 \(i\) 堆放了 \(j\) 个石子,偶数位异或和为 \(k\) 的方案数。3D / 1D 动态规划,时间复杂度 \(\mathcal O(n^3m)\)。

因为和位运算相关,各位之间独立,那么考虑按位拆分。此处我没有想到是因为以前没有见过这种类型的 DP。

设 \(f(i,j)\) 表示前 \(i\) 个二进制位上偶数位石子异或和均为 0 的方案数。

考虑 \(i+1\) 位,显然要往偶数位上放 \(k(2|k)\) 个石子,造成的影响为 \(k\times 2^i\),偶数位上选 \(k\) 个位置的方案数为 \(\dbinom{\lfloor\frac{m+1}{2} \rfloor}{k}\)。

综上,有:

\[f(i,j)=\sum_{2|k,k\le \lfloor\frac{m+1}{2} \rfloor,k\times 2^{i-1}\le j} f(i-1,j-k\times 2^{i-1})\times \binom{\lfloor \frac{m+1}{2}\rfloor }{k} \]

然后最后再用组合数算一下即可。时间复杂度 \(\mathcal O(nm\log n)\),用一些内存连续访问之类的卡常技巧足以通过。

// Problem: P5363 [SDOI2019]移动金币
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5363
// Memory Limit: 500 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

const int maxn = 1.5e5 + 5;
const int maxm = 22;
const int mod = 1e9 + 9;
int n,m,fac[maxn],inv[maxn],f[maxm][maxn],S,p,q;

void add(int& x,int y) {
	x += y;
	if(x >= mod)
		x -= mod;
	return ;
}

void sub(int& x,int y) {
	x -= y;
	if(x < 0)
		x += mod;
	return ;
}

int power(int x,int y) {
	int ans = 1;
	for(;y;y >>= 1) {
		if(y & 1)
			ans = 1ll * ans * x % mod;
		x = 1ll * x * x % mod;
	}
	return ans;
}

int C(int n,int m) {
	if(n < m||n < 0||m < 0)
		return 0;
	return 1ll * fac[n] * inv[n - m] % mod * inv[m] % mod;
}

int main() {
	scanf("%d %d",&n,&m);
	if(n < m) {
		puts("0");
		return 0;
	}
	fac[0] = 1;
	for(int i = 1;i <= n;++ i)
		fac[i] = 1ll * i * fac[i - 1] % mod;
	inv[n] = power(fac[n] , mod - 2);
	for(int i = n - 1;~ i;-- i)
		inv[i] = 1ll * (i + 1) * inv[i + 1] % mod;
	n -= m;
	p = (m + 1) >> 1;
	q = m + 1 - p;
	S = std::log(n) / std::log(2) + 2;
	f[0][0] = 1;
	for(int i = 1;i <= S;++ i)
		for(int j = 0;j <= n;++ j)
			for(int k = 0;k <= p&&k * (1 << (i - 1)) <= j;k += 2)
				add(f[i][j] , 1ll * f[i - 1][j - k * (1 << (i - 1))] * C(p , k) % mod);
	int ans = C(n + m , m);
	for(int i = 0;i <= n;++ i)
		sub(ans , 1ll * f[S][i] * C(n - i + q - 1 , q - 1) % mod);
	printf("%d\n",ans);
	return 0;
}

标签:偶数,return,int,题解,石子,金币,异或,SDOI2019,mod
From: https://www.cnblogs.com/663B/p/17183180.html

相关文章

  • AcWing 4490. 染色题解
    题目描述样例输入:612215211111输出3算法描述思路我们以样例为例讲讲思路。如何确保dfs能顺利便利呢,我们可以使用链式前向星来存图(树)C++代......
  • AcWing 4495. 数组操作题解
    思路此题较为简单,简述一下思路。从小到大排序,每次选取最小值,只要不为0即可每次都为序列减去一个数字太慢,但每个数又减去的数字一样,所以可以用minus记录每个数要减去的数......
  • 3.2 L5-NOIP训练29 测试题解
    3.2L5-NOIP训练29测试题解码创Contest#530(出题人写中文也要句句都打分号吗!!)A.老司机的压缩包(数论)题面老司机最近得到了一个奇怪的压缩包,听说里面有十分厉害的东西......
  • 3 月 1 日测试题解
    3月1日测试题解T1题意给你一个\(n\timesm\)的01矩形,求一个面积最大的不包含数字1的矩形。\(n,m\le1000\)。思路首先,这道题的数据水到了什么程度呢?\(O(n......
  • MySQL Workbench 8.0 点击Server Status面板Could not acquire management access for
    转载自:MySQLWorkbench8.0点击ServerStatus面板Couldnotacquiremanagementaccessforadministration报错问题解决Win10安装MySQLWorkbench8.0后连接MySQL服务......
  • LG-P3603 雪辉 题解
    LG-P3603雪辉Solution目录LG-P3603雪辉Solution更好的阅读体验戳此进入题面SolutionCodeUPD更好的阅读体验戳此进入题面给定$n$个点的树,存在点权,多次询问每次......
  • [ABC273G] Row Column Sums 2 题解
    [ABC273G]RowColumnSums2Solution目录[ABC273G]RowColumnSums2Solution更好的阅读体验戳此进入题面SolutionCodeUPD更好的阅读体验戳此进入题面给定$n$,给......
  • 力扣第335场周赛补题题解
    目录1.递枕头2.二叉树中的第K大层和3.分割数组使乘积互质4.获得分数的方法数1.递枕头classSolution{public:intpassThePillow(intn,inttime){......
  • [ABC274E] Booster 题解
    [ABC274E]BoosterSolution目录[ABC274E]BoosterSolution更好的阅读体验戳此进入题面SolutionCodeUPD更好的阅读体验戳此进入题面在经典的TSP问题基础上存在初始......
  • 题解:【ABC292F】 Regular Triangle Inside a Rectangle
    题目链接不妨设\(a\leb\)。显然当三角形三个点都在矩形边上的时候可以得到答案。通过手玩我们可以发现,当正方形推广到矩形的过程中,我们将一边拉长,三角形就可以不断往......