当前位置:网站首页>2020ccpc Weihai J - Steins; Game (SG function, linear basis)
2020ccpc Weihai J - Steins; Game (SG function, linear basis)
2022-07-07 09:48:00 【moyangxian】
The question :n Rubble , Each pile of stones has two colors black and white , When taking black stones, you must take the least amount ( At least one ), There is no limit to white, you can take it at will ( At least one ). The backhand can dye all the stones before the game starts , Ask the number of coloring schemes that the backhand can win .
Answer key : First, you can divide black and white into two games , The XOR sum of two games is 0 That is, the backhand wins .
White game : amount to nim game
Black game : adopt sg You can find
SG value = Minimum number of stones − ( ( Minimum number of heaps + [ The number of all stones is the same ] ) % 2 )
Can find sg The value is only related to the smallest heap , Then we can enumerate the smallest heap . Use one pre Maintain XOR prefix and ,suf Maintain XOR suffixes and , Maintain a linear basis from back to front . Because the heap we enumerated is the smallest heap , Therefore, the pile with less stones than the current enumeration must be white , We want the final total XOR value to be 0, Then it depends on whether the linear basis can satisfy XOR and as 0 Number of numbers , Scheme i.e 2 Of (s - tot) Power . Finally, multiply by a combined number . The detailed code can be seen .
sg Function table code :
#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;
}
Title code :
#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;// Record the plan
int x = pre[i - 1];// Prefix exclusive or and
int y = a[i] - ((same[i] + 1) & 1);
// Currently selected same[i] The number of pieces is a[i] The stone pile is dyed black ( All stone heaps have the same number of stones )
int z = suf[i + same[i]];// Suffix XOR and
if ((x ^ y ^ z) == 0) sum = (sum + 1) % mod;// If XOR and is 0, Method number plus one
y = a[i] - (same[i] & 1);// ditto y, But the number of stones in all stone piles is different
int need = x ^ y;// Satisfy XOR and do 0 Number of numbers
if (LB.count(need)) sum = (sum + qpow(2, n - head + 1 - LB.tot)) % mod;
// If need It can be expressed by linear basis , The scheme that the linear basis can express this number is 2^(s - tot)
//s Is the number of linear basis insertions ,tot Is the number in the linear base
if ((need ^ suf[i + same[i]]) == 0) sum = (sum - 1 + mod) % mod;
// If the suffix all numbers are XOR and equal need Then the number of schemes should be reduced by one
if (same[i - 1] == 1) {
// If it is currently a[i] The last stone pile of the quantity , Set all values to a[i] Insert the number of into the linear base
for (int j = 1; j <= same[i]; j++) LB.insert(a[i]);
head = i;
}
ans = (ans + sum * C(num[i], same[i]) % mod) % mod;
// Finally, take the bus at num[i] Middle selection same[i] Number of heap methods
}
cout << ans << endl;
return 0;
}
边栏推荐
- 如何成为一名高级数字 IC 设计工程师(1-6)Verilog 编码语法篇:经典数字 IC 设计
- Octopus future star won a reward of 250000 US dollars | Octopus accelerator 2022 summer entrepreneurship camp came to a successful conclusion
- IIS redirection redirection appears eurl axd
- 根据热门面试题分析Android事件分发机制(一)
- 进程间的通信方式
- 小程序滑动、点击切换简洁UI
- 【无标题】
- JS judge whether checkbox is selected in the project
- Information Security Experiment 3: the use of PGP email encryption software
- Diffusion模型详解
猜你喜欢
Basic use of JMeter to proficiency (I) creation and testing of the first task thread from installation
战略合作|SubQuery 成为章鱼网络浏览器的秘密武器
使用BigDecimal的坑
CentOS installs JDK1.8 and mysql5 and 8 (the same command 58 in the second installation mode is common, opening access rights and changing passwords)
Information Security Experiment 1: implementation of DES encryption algorithm
Oracle安装增强功能出错
【BW16 应用篇】安信可BW16模组/开发板AT指令实现MQTT通讯
Octopus future star won a reward of 250000 US dollars | Octopus accelerator 2022 summer entrepreneurship camp came to a successful conclusion
What development models did you know during the interview? Just read this one
Pit using BigDecimal
随机推荐
Netease cloud wechat applet
flinkcdc采集oracle在snapshot阶段一直失败,这个得怎么调整啊?
sql 里面使用中文字符判断有问题,哪位遇到过?比如value&lt;&gt;`无`
基于智慧城市与储住分离数字家居模式垃圾处理方法
[4g/5g/6g topic foundation -147]: Interpretation of the white paper on 6G's overall vision and potential key technologies -2-6g's macro driving force for development
thinkphp数据库的增删改查
12、 Sort
小程序滑动、点击切换简洁UI
【frida实战】“一行”代码教你获取WeGame平台中所有的lua脚本
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
第一讲:鸡蛋的硬度
shake数据库中怎么使用Mongo-shake实现MongoDB的双向同步啊?
Netease Cloud Wechat applet
Dynamics 365Online ApplicationUser创建方式变更
Switching value signal anti shake FB of PLC signal processing series
NATAPP内网穿透
Information Security Experiment 2: using x-scanner scanning tool
VSCode+mingw64+cmake
Lecture 1: stack containing min function
第十四次试验