当前位置:网站首页>2020CCPC威海 J - Steins;Game (sg函数、线性基)
2020CCPC威海 J - Steins;Game (sg函数、线性基)
2022-07-07 07:09:00 【moyangxian】
题意:n堆石子,每堆石子有黑和白两种颜色,拿黑色堆石子的时候必须拿数量最少的(最少一个),白色没有限制可以任意拿(最少一个)。后手的人可以在游戏开始之前对所有石子堆染色,问后手能赢的染色方案数。
题解:首先可以将黑色和白色分成两个游戏,两个游戏的异或和为0即后手胜利。
白色游戏:相当于nim游戏
黑色游戏:通过sg打表能发现
SG值 = 最小堆石子数 − ( ( 最小堆数量 + [ 所有堆石子数相同 ] ) % 2 )
能发现sg值只跟最小堆有关系,然后我们可以枚举最小堆。用一个pre维护异或前缀和,suf维护异或后缀和,从后往前维护一个线性基。由于我们枚举到的堆是最小堆,所以石子数量比当前枚举的堆要少的一定是白色,我们要最后总的异或值为0,那么要看线性基里能不能表示出满足异或和为0的数,方案即 2的(s - tot)次方。最后再乘上一个组合数即可。具体细节代码可见。
sg函数打表代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int sg[N];
int SG(priority_queue<int, vector<int>, greater<int> > q) {
bool vis[N] = {
false };
if (q.empty()) return 0;
int t = q.top();
q.pop();
vis[SG(q)] = true;
for (int i = 1; i < t; i++) {
auto tmp = q;
tmp.push(t - i);
vis[SG(tmp)] = true;
}
for (int i = 0; ; i++)
if (!vis[i]) return i;
}
int main() {
priority_queue<int, vector<int>, greater<int> > q;
for (int i = 0; i <= 5; i++) {
for (int j = i; j <= 5; j++) {
for (int k = j; k <= 5; k++) {
for (int l = k; l <= 5; l++) {
for (int r = l; r <= 5; r++) {
while (!q.empty()) q.pop();
if (i) q.push(i), cout << i << " ";
if (j) q.push(j), cout << j << " ";
if (k) q.push(k), cout << k << " ";
if (l) q.push(l), cout << l << " ";
if (r) q.push(r), cout << r << " ";
cout << " : " << SG(q) << endl;
}
}
}
}
}
return 0;
}
题目代码:
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
int f[N], inv[N];
int a[N], pre[N], suf[N];
int same[N], num[N];
map<int, int> t;
struct LB {
const static int N = 64;
ll a[N + 1], tot;
LB() {
memset(a, 0, sizeof(a)), tot = 0; }
bool insert(ll x) {
for (int i = N; i >= 0; i--) {
if (x & (1ll << i)) {
if (a[i]) x ^= a[i];
else {
a[i] = x;
tot++;
break;
}
}
}
return x > 0;
}
bool count(ll x) {
for (int i = N; i >= 0; i--)
if (x & (1ll << i)) x ^= a[i];
return x == 0;
}
}LB;
int qpow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
void init(int n) {
f[0] = inv[0] = 1;
for (int i = 1; i <= n; i++)
f[i] = f[i - 1] * i % mod;
inv[n] = qpow(f[n], mod - 2);
for (int i = n - 1; i >= 1; i--)
inv[i] = inv[i + 1] * (i + 1) % mod;
}
int C(int a, int b) {
if (a < b) return 0;
return f[a] * inv[b] % mod * inv[a - b] % mod;
}
signed main() {
init(N - 1);
int n;
cin >> n;
int ans = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
t[a[i]]++;
ans ^= a[i];
}
ans = (ans == 0 ? 1 : 0);
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++)
pre[i] = pre[i - 1] ^ a[i];
for (int i = n; i >= 1; i--)
suf[i] = suf[i + 1] ^ a[i];
for (int i = n; i >= 1; i--) {
same[i] = (a[i] == a[i + 1] ? same[i + 1] + 1 : 1);
num[i] = t[a[i]];
}
int head = n + 1;
for (int i = n; i >= 1; i--) {
int sum = 0;//记录方案
int x = pre[i - 1];//前缀异或和
int y = a[i] - ((same[i] + 1) & 1);
//当前选了same[i]个数量为a[i]的石堆染成黑色(所有石堆石子数相同)
int z = suf[i + same[i]];//后缀异或和
if ((x ^ y ^ z) == 0) sum = (sum + 1) % mod;//如果异或和为0,方法数加一
y = a[i] - (same[i] & 1);//同上y,但是所有石堆石子数不相同
int need = x ^ y;//满足异或和为0的数
if (LB.count(need)) sum = (sum + qpow(2, n - head + 1 - LB.tot)) % mod;
//如果need能用线性基表示出来,线性基能表示出这个数的方案为2^(s - tot)
//s为线性基插入次数,tot为线性基内的个数
if ((need ^ suf[i + same[i]]) == 0) sum = (sum - 1 + mod) % mod;
//如果后缀所有数异或和等于need那么方案数要减一
if (same[i - 1] == 1) {
//如果当前是a[i]数量的最后一个石堆,把所有值为a[i]的数插入到线性基中
for (int j = 1; j <= same[i]; j++) LB.insert(a[i]);
head = i;
}
ans = (ans + sum * C(num[i], same[i]) % mod) % mod;
//最后要乘上在num[i]中选same[i]堆的方法数
}
cout << ans << endl;
return 0;
}
边栏推荐
- Create an int type array with a length of 6. The values of the array elements are required to be between 1-30 and are assigned randomly. At the same time, the values of the required elements are diffe
- 消费互联网的产业链其实是很短的,它仅仅承接平台上下游的对接和撮合的角色
- Huawei hcip datacom core_ 03day
- [bw16 application] Anxin can realize mqtt communication with bw16 module / development board at instruction
- **Grafana installation**
- 信息安全实验二 :使用X-SCANNER扫描工具
- Jenkins+ant+jmeter use
- Difference between interface iterator and iteratable
- esp8266使用TF卡并读写数据(基于arduino)
- 用flinksql的方式 写进 sr的表,发现需要删除的数据没有删除,参照文档https://do
猜你喜欢
农牧业未来发展蓝图--垂直农业+人造肉
How will fashion brands enter the meta universe?
十二、排序
Vs2013 generate solutions super slow solutions
What development models did you know during the interview? Just read this one
[cloud native] Devops (I): introduction to Devops and use of code tool
【无标题】
iNFTnews | 时尚品牌将以什么方式进入元宇宙?
Diffusion模型详解
Information Security Experiment 3: the use of PGP email encryption software
随机推荐
Nested (multi-level) childrn routes, query parameters, named routes, replace attribute, props configuration of routes, params parameters of routes
Loxodonframework quick start
Yapi test plug-in -- cross request
【BW16 应用篇】安信可BW16模组/开发板AT指令实现MQTT通讯
NATAPP内网穿透
基于智慧城市与储住分离数字家居模式垃圾处理方法
Windows starts redis service
消费互联网的产业链其实是很短的,它仅仅承接平台上下游的对接和撮合的角色
信息安全实验二 :使用X-SCANNER扫描工具
细说Mysql MVCC多版本控制
H5网页播放器EasyPlayer.js如何实现直播视频实时录像?
How to speed up video playback in browser
Difference between process and thread
Binary tree high frequency question type
Arthas simple instructions
第一讲:寻找矩阵的极小值
liunx命令
Vs2013 generate solutions super slow solutions
# Arthas 简单使用说明
scrapy爬虫mysql,Django等