省选模拟五十六 题解(示例代码)

athosd 2021-03-03

栏目: 类库 ·

来源: athosd

作者:athosd

简介  这篇文章主要介绍了省选模拟五十六 题解(示例代码)以及相关的经验技巧,文章约1363字,浏览量322,点赞数2,值得参考!

T1
异或和为0则先手必败
(dp[i][j][k])代表考虑到(i)选了(j)个数(对(d)取模)异或和为(k)的方案数
假如把(a)从大到小排序的话便可以剪枝:
第三维是(2^b)(b是满足(2^b>a[i])的第一个数)
复杂度(O(1e7*d))

T2
(f[i][j][k])代表从S走k步到T不经过S,T的方案数
(g[i][j][k])代表从S走k步到T的方案数
(h[i][j][k])代表从S走k步到S不经过T的方案数
(g)可以暴力求出来
则有转移:
(f[S][T][d]=g[S][T][d]-sum_{i=1}^{d-1}f[S][T][i]*g[T][T][d-i]+h[S][T][i]*g[S][T][d-i])
(h[S][T][d]=g[S][T][d]-sum_{i=1}^{d-1}h[S][T][i]*g[S][S][d-i]+f[S][T][i]*g[T][S][d-i])
很教科书

T3
打暴力会发现可以把行列交换
(f[i])代表(i)这行是否被操作,(g[i])是列
那么这轮后((i,j))变成(f[i] xor g[j])
然后把f/g=1的全部放到上/左面
现在便成了一个(2*2)的矩阵
每个矩阵里的数字在第一轮及以后后一定都是一样的
拿线段树求出初始状态后模拟即可


以上就是本文的全部内容,希望对大家的学习有所帮助,本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 原文地址:https://www.cnblogs.com/AthosD/p/12589845.html

相关文章

省选模拟三十五题解(示例代码)

省选模拟三十四 题解(示例代码)

[noi.ac省选模拟赛]第10场题解集合

[noi.ac省选模拟赛]第12场题解集合

一个被不点名批评的垃圾骗分暴力选手被普及难度的省选信心(??)模拟赛艹爆的题解

省选模拟24(示例代码)

省选模拟2(示例代码)

2019/3/11 省选模拟总结(示例代码)