异或帽子（hat）
显然，
\[B_i = (\oplus_{j=1}^{n} A_j) \oplus A_i \]因为 \(2 | n\)，所以：
\[S = \oplus_{i=1}^{n}B_i = \oplus_{i=1}^{n}A_i \]那么
\[A_i = S \oplus B_i \]#include<bits/stdc++.h>
using namespace std;
int n;
int s;
int a[200005];
signed main()
{
freopen("hat.in","r",stdin);
freopen("hat.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
s ^= a[i];
}
for(int i=1;i<=n;i++)
{
int tp = s ^ a[i];
printf("%d ",tp);
}
}
传话游戏（string）
令 \(f_i\) 表示 \([1,i]\) 中的所有数按规则交换的方案数。
显然，对于单词 \(i\) 来说，仅当单词 \(i-1\) 不同于 \(i\) 时交换才有意义。
故：
\[f_i = f_{i-1} + [S_i \not= S_{i-1}]f_{i-2} \]#include<bits/stdc++.h>
#define ll long long
const int mod = 1e9 + 7;
using namespace std;
int n;
string a[100005];
int cnt;
ll f[100005];
signed main()
{
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
f[1] = 1;
f[2] = 2 - (a[1] == a[2]);
for(int i=3;i<=n;i++)
{
f[i] = f[i-1];
if(a[i] != a[i-1])
{
f[i] = (f[i] + f[i-2]) % mod;
}
}
printf("%lld",f[n]);
return 0;
}
全球覆盖（globe）
发现两个维度间相互独立，考虑分开处理。
考虑若干线段，令线段 \(i\) 的权为 \(2^i\)（即在线段首尾位置附上 \(2_i\)），则区间异或和相同的地方为同种方案。
但线段数过大，考虑随机化算法随机赋权，第 \(i\) 条线段权为 \(2^{rnd}\)。
考虑生日悖论，正确概率为
\[\prod_{k=0}^{2n-1}(1-\frac{k}{2^{64}})^2 \]运气别太烂应该都能过。
#include<bits/stdc++.h>
#define int unsigned long long
#define pii pair<unsigned long long,unsigned long long>
#define mp make_pair
using namespace std;
mt19937_64 rng(random_device{}());
int n,X,Y;
pii xx[500005],yy[500005];
int solve(pii *a,int up)
{
vector<pii> x,y;
x.clear();
y.clear();
for(int i=1,tmp=rng();i<=n;i++,tmp=rng())
{
x.push_back(mp(a[i].first,tmp));
x.push_back(mp(a[i].second,tmp));
}
x.push_back(mp(0,0));
x.push_back(mp(up,0));
sort(x.begin(),x.end());
for(int i=0,sz=x.size()-1,tmp=0;i<sz;i++)
{
tmp ^= x[i].second;
y.push_back(mp(tmp,x[i+1].first - x[i].first));
}
sort(y.begin(),y.end());
int res = 0;
for(int i=0,sz=y.size(),tmp=0;i<sz;i++)
{
if(i == 0 || y[i].first == y[i-1].first)
{
tmp += y[i].second;
}
else tmp = y[i].second;
res = max(res,tmp);
}
return res;
}
signed main()
{
freopen("globe.in", "r", stdin);
freopen("globe.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>X>>Y;
for(int i=1;i<=n;i++)
{
cin>>xx[i].first>>yy[i].first>>xx[i].second>>yy[i].second;
}
cout<<solve(xx,X) * solve(yy,Y);
}
幂次序列（sequence）
求的是区间贡献。
暴力时间复杂度太高，考虑 CDQ 分治。
显然，区间 \([i,i]\) 的贡献为 \(1\)。
考虑已经完成区间 \([l,mid]\) 与 \([mid+1,r]\) 的贡献统计。
发现性质：若区间最值为 \(2^x\)，则区间和不超过 \(2^{x + \log{n}}\)。
扫描区间最值，另一侧使用哈希储存后缀（或前缀），统计即可。
得卡卡常。
#pragma GCC optimize(3)
#pragma GCC optimize(2)
#pragma GCC optimize("inline")
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
ull fpow(ull b, ull mod) {
ull r = 1, a = 2;
while (b) {
if (b & 1)
r = r * a % mod;
a = a * a % mod;
b >>= 1;
}
return r;
}
int n, a[200005];
ull pw1[200005], pw2[200005];
int ans;
ull sum1[200005], sum2[200005];
const ull mod1 = 1e9 + 7, mod2 = 998244353;
ull hsh(int w, int k, int idx) {
return (((ull)pw1[w] << k) - sum1[idx] + mod1) % mod1 * ((((ull)pw2[w] << k) - sum2[idx] + mod2) % mod2);
}
unordered_map<ull, int> mp;
void cdq(int l, int r) {
if (l == r) {
ans++;
return;
}
int mid = (l + r) >> 1;
cdq(l, mid);
cdq(mid + 1, r);
sum1[mid] = pw1[mid];
sum1[mid + 1] = pw1[mid + 1];
sum2[mid] = pw2[mid];
sum2[mid + 1] = pw2[mid + 1];
for (int i = mid + 2; i <= r; i++) {
sum1[i] = (sum1[i - 1] + pw1[i]) % mod1;
sum2[i] = (sum2[i - 1] + pw2[i]) % mod2;
}
for (int i = mid - 1; i >= l; i--) {
sum1[i] = (sum1[i + 1] + pw1[i]) % mod1;
sum2[i] = (sum2[i + 1] + pw2[i]) % mod2;
}
mp.clear();
for (int i = mid + 1, mx = mid + 1, p = mid; i <= r; i++) {
if (a[i] > a[mx])
mx = i;
while (p >= l && a[p] < a[i]) ++mp[sum1[p] * sum2[p]], p--;
for (int j = 0; j <= 20; j++) {
if (mp.count(hsh(mx, j, i)))
ans += mp[hsh(mx, j, i)];
}
}
mp.clear();
for (int i = mid, mx = mid, p = mid + 1; i >= l; i--) {
if (a[i] > a[mx])
mx = i;
while (p <= r && a[p] <= a[i]) ++mp[sum1[p] * sum2[p]], p++;
for (int j = 0; j <= 20; j++) {
if (mp.count(hsh(mx, j, i)))
ans += mp[hsh(mx, j, i)];
}
}
}
signed main() {
freopen("sequence.in", "r", stdin);
freopen("sequence.out", "w", stdout);
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
pw1[i] = fpow(a[i], mod1);
pw2[i] = fpow(a[i], mod2);
}
cdq(1, n);
cout << ans;
return 0;
}