Xor on permutation
作用在排列上的异或运算
也不知道这一部分放在哪个类别下比较好,姑且放在数论下面了
前置知识
排列和置换
引入
偶尔在做算法题的时候会遇到需要研究一个区间的数都异或上一个数之后，这个区间的数的情况(这里情况指各种各样的性质)。不过我们可以把任意区间\([l,r]\)转化成两个排列\(P_{r},P_{l-1}\)的差。所以我们试图借助几个例题来研究排列异或一个数之后具有的性质。
以下是3个例题：
CF1979B XOR
Sequences
CF2075E XOR
Matrix
CF
Group:0x3f vp Group FireflyCup H Simple XOR Problem
分析
我们考虑一个无穷序列\(0,1,2,...\)异或上一个数\(x\)的情况。
显然，我们应该把\(x\)拆成不同二进制位来分析，或者说异或\(x\)的效果实际上是异或上\(x\)不同二进制位的效果的叠加。
于是我们可以转而分析异或\(2\)的自然数次幂的作用。
1. 如果\(xor 1\),序列变成\(1,0,3,2,5,4,...\),相当于把相邻两位做一个对换。
2. 如果\(xor 2\),序列变成\(2,3,0,1,6,7,4,5,...\)相当于相邻2位一组，把相邻两组做一个对换。
3. 如果\(xor
2^k\),可以类比推得：相当于每\(2^k\)一组，顺次把每两组做一个对换。
可以发现，\(xor
2^k\)的影响区间是一段一段的(只有段内的对换，段之间没有对换)，每段之间没有干涉，段长是\(2^{k+1}\)。我们可以先来看看段内之间的作用。
实际上段内的作用简单：\(xor
k\)的作用即为把一段的前半部分和后半部分对换，每半部分内部的顺序保持不变。
如果用置换的语言来描述的话，就是：
\[Xor 2^k = \sum_{i = 0}^{\infty} \sigma_k(i)
,\\ \sigma_k(i) = \begin{pmatrix}
i \cdot 2^{k+1} + 0 & i \cdot 2^{k+1} + 1 & i \cdot
2^{k+1} + 2 & ... & i \cdot 2^{k+1} + 2^k - 1 & ...
& i \cdot 2^{k+1} + 2^{k+1} - 1\\
i \cdot 2^{ k+1} + 2^k & i \cdot 2^{k+1} + 2^k+1 & i \cdot
2^{k+1} +2^k +2 & ... & i \cdot 2^{k+1} + 2^{k+1} - 1 & ...
&i \cdot 2^{k+1} + 2^k - 1
\end{pmatrix}\]
而且实际上这是一个自然数集上的双射。
我们考虑其中一个trivial的置换在有限排列上的作用，即
\[\sigma_k = \begin{pmatrix}
0 & 1 & 2 & ... & 2^k - 1 & 2^k &
... & 2^{k+1} - 1\\
2^k & 2^k+1 & +2^k +2 & ... & 2^{k+1} - 1 & 0
&...& 2^k - 1
\end{pmatrix}\]
- 如果排列长度\(n \geq
2^{k+1}-1\),那么会对这个排列的前面这一段做一个对半的对换，作用后这一段在值域上仍保持连续。
- 如果排列长度\(n
< 2^{k+1}-1\),具体情况还可以再分类讨论：
- 如果\(n \leq
2^{k}-1\),那么这个排列将整体加上\(2^k\)。
- 如果\(n \geq 2^k\),那么这个排列被作用后，值域上变成不连续的两部分,其中一部分\(length \leq 2^{k}-1\),一部分\(n = 2^{k}-1\)。
- 如果\(n \leq
2^{k}-1\),那么这个排列将整体加上\(2^k\)。
根据我们前面的分析，我们可以得到一些推论，用于解决以上给出的3个例题。
- 对于一个区间\([l,r]\),它异或上一个数\(x\)后，在值域上最多形成\(O(\log x)\)个连续区间
>\(Proof\)：
我们从高位到低位去考虑异或一个数的影响。
根据我们前面所做的讨论，对于\(x\)的最高位，一个连续区间最多只有左右两端的部分(块长不足\(2^{k+1}-1\),即情况2)会被"切割"开。
考虑其中被切割出来的一块(不妨设为右边那块)，它的左端点原来为\(i \cdot 2^{k+1}\),被置换到了\((i + 1) \cdot 2^{k + 1} - 1\)作为右端点。那么对于次高位，一定是不能从这一块的右端"切割"出一块的。
递归地考虑：除了最高位，每一位最多可以在上一位切割出来的新块上多切割出一块(因为被切出来的新块已经对齐一端了)。
那么实际上最多切割出\(2 \log x\)块。而且平均值是小于\(\log x\)的。
> 这里有一个可以用来直观感受一下的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
using ll = long long;
using ull = unsigned long long;
using i64 = long long;
using uint = unsigned int;
using namespace std;
void solve()
{
mt19937 g(chrono::steady_clock::now().time_since_epoch().count());
constexpr int inf = 1<<20;
int l = g() % inf, r = g() % inf;
if (l > r)swap(l, r);
int x = g() % inf;
vector<int>a(1 << 21 + 1);
for (int i = l; i <= r; i++) {
a[i ^ x] = 1;
}
//output
int cnt = 0;
vector<pair<int, int>>ranges;
int in = 0;
pair<int, int>pr;
for (int i = 0; i < (1 << 21) + 1; i++) {
if (a[i] == 0) {
if (in) {
in = false;
ranges.push_back(pr);
}
}
else {
if (in)
pr.second = i;
else {
in = true;
pr.first = i;
pr.second = i;
}
}
}
cout << "l : " << l << " r : " << r << " x : " << x << endl;
cout << "ranges cnt : " << ranges.size() << endl;
for (auto [l, r] : ranges) {
cout << l << " " << r << endl;
}
return;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int tt;
cin >> tt;
while (tt--)
solve();
return 0;
} - 对于一个排列\(P_n\),记异或上\(x\)之后,小于等于\(n\)的数的个数为\(f_n(x)\)。
有：- \(f_n(x) = f_n(y) \quad\quad if \quad highbit(x) = highbit(y)\)
- \(f_n(x) \leq f_n(y) \quad\quad if \quad
highbit(x) > highbit(y)\) >\(Proof\):
对第一条，\(x,y\)最高位\(2^k\)的影响是相同的。仅考虑最高位影响，显然只有最右端的置换\(\sigma_k(\left\lfloor\frac{n}{2^{k+1}}\right\rfloor)\)会影响答案。
考虑前面我们讨论过的\(\sigma_k\)作用在\(P_n\)的情况(这里的\(n\)和前面的不一样了)，如果是\(n <2^k\)，这一段被全部换到大于等于\(2^k\)的位置，不管低位的置换作用是什么样子，这一段都会一直大于等于\(2^k\),贡献为0。
如果是\(n \leq 2^k\),会有\(n - 2^k + 1\)个大于等于\(2^k\)的数被换到左边。具有贡献，同时小于\(2^k\)的数占满了大于等于\(2^k\)的位置，其中\(n - 2^k + 1\)个位置有贡献。而无论低位的等效置换怎么换，产生的贡献是不变的。
所以\(f_n(x)\)的值仅和\(x\)的\(highbit\)有关。
对于第二条，正向不太好说。但是我们可以逆向理解贡献的计算：\(n\)减去被换到\(0\sim n\)区域的大于\(n\)的数。而我们可以观察到：高位越大，最右端的置换包含的超出\(n\)的部分是不减的。可以比较直观地感受到第二条。(严谨一些的解释的话情况比较多，写起来有点麻烦(好吧就是我懒了))。
> 下面来看看上面提到的3个题。
T1 CF1979B XOR Sequences
一道简单的div2B 猜猜题。
题意大概是\(P_{\infty}\)分别异或\(x,y\)得到\(a,b\),求\(a,b\)的最长公共子段(LCS)。
我们从置换叠加的角度去分析：
如果\(a\)有\(\sigma_k\)作用而\(b\)没有，那么LCS最多长\(2^k\)。
所以实际上我们是在找\(x,y\)从低到高第一个不同的二进制位。
如果是第k位，那么答案为\(2^k\)。
T2 CF2075E XOR Matrix
div2E 思维题？
题意是在\(n\)行\(m\)列的矩阵的行和列上填上一些数，行，列的值域分别为\([0,x],[0,y]\)。矩阵\(a_{ij}\)的值为\(r_i \oplus
c_j\)。要求矩阵的值最多只有2种，问合法的填法数目。
首先，一行/列最多出现2种不同的值，因为异或是一个双射，3种不同值一定有3种结果，此时是不合法的。
于是我们可以分讨一下：
用\(a +
b\)表示我们行和列选几个不同的数。
1. \(1+1\),此时很简单，一共\((x+1)(y+1)\)种填法。
2. \(1+2 /
2+1\)。任意选2个数填充行/列即可，这里需要考虑2种数的填法，减去退化成\(1+1\)的情况。
一共\(\tbinom{x+1}{2}*(2^n - 2)*(y+1) +
\tbinom{y+1}{2}*(2^m - 2)*(x+1)\)种填法
3. \(2+2\)此时比较复杂。我们先考虑什么时候是合法的：4个数的异或只有2种结果。实际上，我们可以选择行填充\(\{i,i\oplus k\}\),列填充\(\{j ,j \oplus k\}\),那么结果只有\(i\oplus j, i\oplus j\oplus
k\)两种，符合题意。其次我们考虑这形如这样的构造是否遍历到了所有的合法构造方法。实际上答案是肯定的。（这里可以仔细思考一下为什么）
不过这里我们\(k\)从1开始取，不然就退化了。
然后就是对于每个\(k\)，找出合法的\(i,j\)的数目(为了避免重复，每对\(\{i,i \oplus k\}\)只算一个)，即\(i < i\oplus k\leq n\),\(j\)类似。暴力肯定是不可取的。根据我们前面的推论，实际上每个对于\(highbit\)相等的\(k\)，这个值是相等的。于是我们可以枚举\(k = 2^r\)的情况，每次一起计算\(highbit\)相同的\(k\)的答案即可。
代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
using ll = long long;
using ull = unsigned long long;
using i64 = long long;
using uint = unsigned int;
using namespace std;
constexpr int mod = 998244353;
template<class T>
constexpr T power(T a, i64 b) {
T res{ 1 };
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
constexpr i64 mul(i64 a, i64 b, i64 p) {
i64 res = a * b - i64(1.L * a * b / p) * p;
res %= p;
if (res < 0) {
res += p;
}
return res;
}
template<i64 P>
struct MInt {
i64 x;
constexpr MInt() : x{ 0 } {}
constexpr MInt(i64 x) : x{ norm(x % getMod()) } {}
static i64 Mod;
constexpr static i64 getMod() {
if (P > 0) {
return P;
}
else {
return Mod;
}
}
constexpr static void setMod(i64 Mod_) {
Mod = Mod_;
}
constexpr i64 norm(i64 x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr i64 val() const {
return x;
}
constexpr MInt operator-() const {
MInt res;
res.x = norm(getMod() - x);
return res;
}
constexpr MInt inv() const {
return power(*this, getMod() - 2);
}
constexpr MInt& operator*=(MInt rhs)& {
if (getMod() < (1ULL << 31)) {
x = x * rhs.x % int(getMod());
}
else {
x = mul(x, rhs.x, getMod());
}
return *this;
}
constexpr MInt& operator+=(MInt rhs)& {
x = norm(x + rhs.x);
return *this;
}
constexpr MInt& operator-=(MInt rhs)& {
x = norm(x - rhs.x);
return *this;
}
constexpr MInt& operator/=(MInt rhs)& {
return *this *= rhs.inv();
}
friend constexpr MInt operator*(MInt lhs, MInt rhs) {
MInt res = lhs;
res *= rhs;
return res;
}
friend constexpr MInt operator+(MInt lhs, MInt rhs) {
MInt res = lhs;
res += rhs;
return res;
}
friend constexpr MInt operator-(MInt lhs, MInt rhs) {
MInt res = lhs;
res -= rhs;
return res;
}
friend constexpr MInt operator/(MInt lhs, MInt rhs) {
MInt res = lhs;
res /= rhs;
return res;
}
friend constexpr std::istream& operator>>(std::istream& is, MInt& a) {
i64 v;
is >> v;
a = MInt(v);
return is;
}
friend constexpr std::ostream& operator<<(std::ostream& os, const MInt& a) {
return os << a.val();
}
friend constexpr bool operator==(MInt lhs, MInt rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MInt lhs, MInt rhs) {
return lhs.val() != rhs.val();
}
friend constexpr bool operator<(MInt lhs, MInt rhs) {
return lhs.val() < rhs.val();
}
};
template<>
i64 MInt<0>::Mod = 998244353;
//i64 MInt<0>::Mod = 1000000007;
using Z = MInt<0>;
ll qpow(ll a, int p)
{
ll res = 1;
while (p != 0) {
if (p & 1)res = res * a % mod;
a = a * a % mod;
p >>= 1;
}
return res;
}
void solve()
{
int n, m;
cin >> n >> m;
int x, y;
cin >> x >> y;
vector<int>cntx(30), cnty(30);
Z ans = 0;
ll np = qpow(2, n), mp = qpow(2, m);
//1+1
ans += Z(1) * (x + 1) * (y + 1);
//1+2
ans += Z(1)*x * (x + 1) / 2 * (np - 2) * (y + 1);
ans += Z(1)*y * (y + 1) / 2 * (mp - 2) * (x + 1);
//2+2
//(i,i^k)*(j,j^k)
for (int i = 0; i < 30; i++) {
uint bitmask = ((1u << i + 1) - 1);
cntx[i] = (x & ~bitmask) / 2;
cnty[i] = (y & ~bitmask) / 2;
if (x >> i & 1)cntx[i] += (x & bitmask >> 1) + 1;
if (y >> i & 1)cnty[i] += (y & bitmask >> 1) + 1;
}
for (int i = 0; i < 30; i++) {//comb * ok i * ok j * ok k
ans += Z(1)*(np - 2) * (mp - 2) * cntx[i]*cnty[i]*(1<<i);
}
cout << ans << endl;
return;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int tt;
cin >> tt;
while (tt--)
solve();
return 0;
}
T3 CF Group:0x3f vp Group FireflyCup H Simple XOR Problem
打群友办的比赛碰到的题，也是让我想起来之前的一些想法，最终想出来异或将一个区间划分成\(\log\)个区间的题。但是这题卡常，太坏了！
题意:求和
\[
\sum_{x=l}^{r}\left(x\oplus y\right)^k\pmod{(10^{9}+7)}
\] 其中\(l\), \(r\), \(y\), and \(k\) (\(1\le l\le
r\le 10^9\), \(1\le y\le 10^9\),
\(1\le k\le 10^6\)).
我们需要一些预备知识和技巧：
对于\([l,r]\)上的求和，可以转化成\([0,r]\)上的求和减去\([0,l-1]\)上的求和。
自然数的\(k\)次幂之和是一个\(k+1\)次多项式，这个可以用lagrange插值法在最快\(O(n \log^2 n)\)的复杂度下搞出来。
根据我们前面的推论，我们可以把异或后的值域划分成最多\(log
y\)个连续区间，每个连续区间的贡献我们用自然数\(k\)次幂和公式求出来。形如\([l,r]\)的区间在异或下的端点可能不太好维护，我们可以转成\([1,r]\)这样的区间来解决，这样的区间是好维护的。
最后的复杂度：插值\(O(k \log^2 k)\) +
区间求和\(O(k\log y)\)。
实现代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
using namespace std;
const int mod = 1e9 + 7, N = 1e6 + 10;
ll pre[N], suf[N], finv[N], fact[N], g[N];
ll qmi(ll a, ll k)
{
ll res = 1;
while (k)
{
if (k & 1)res = res * a % mod;
k >>= 1;
a = a * a % mod;
}
return res;
}
void init()
{
fact[0] = 1;
for (int i = 1; i < N; ++i)
fact[i] = fact[i - 1] * i % mod;
finv[N - 1] = qmi(fact[N - 1], mod - 2);
for (int i = N - 1; i >= 1; --i)
finv[i - 1] = finv[i] * i % mod;
}
ll cal(ll* f, int mx, ll n)//已知f[0]到f[mx] 求f[n]
{
if (n <= mx)return f[n];
int ans = 0;
pre[0] = suf[mx] = 1;
for (int i = 1; i <= mx; ++i)
pre[i] = 1ll * (n - i + 1) % mod * pre[i - 1] % mod;//注意到(n-i+1)*pre[i-1]在有些题可能爆ll 先%
for (int i = mx; i >= 1; --i)
suf[i - 1] = 1ll * (n - i) % mod * suf[i] % mod;
for (int i = 0; i <= mx; ++i)
{
int sg = (mx - i) & 1 ? -1 : 1;
ans = ans + 1ll * sg * pre[i] % mod * suf[i] % mod * finv[i] % mod * finv[mx - i] % mod * f[i] % mod;
if (ans >= mod)ans -= mod;
if (ans < 0)ans += mod;
}
return ans;
}
int l, r, y, k;
ll ask(int l, int r) {
if (l)return (cal(g, k + 1, r) - cal(g, k + 1, l - 1)) % mod;
else return cal(g, k + 1, r);
}
ll query(int x) {
int l = 0;
ll res = 0;
for (int i = 30; i >= 0; i--) {
int a = x >> i & 1;
int b = y >> i & 1;
if (a == 0 && b == 0);
else if (a == 1 && b == 1) {
int lq = l + (1 << i);
int rq = l + (1 << (i + 1)) - 1;
res = (res + ask(lq, rq)) % mod;
}
else if (a == 0 && b == 1)l += 1 << i;
else if (a == 1 && b == 0) {
int lq = l;
int rq = l + (1 << i) - 1;
res = (res + ask(lq, rq)) % mod;
l += 1 << i;
}
}
return (res + ask(l, l)) % mod;
}
void solve()
{
cin >> l >> r >> y >> k;
for (int i = 1; i <= k + 1; i++) {
g[i] = (qmi(i, k) + g[i - 1]) % mod;
}
ll res = (query(r) - query(l - 1)) % mod;
cout << (res + mod) % mod << '\n';
}
int main()
{
init();
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
while (t--)solve();
return 0;
}
