problem1 link
给定两个长度都为$n$的数组$A,B$，给出一个操作序列将$A$变成$B$。每个操作可以是以下两种之一：（1）选择一个$i,0leq i <n$且$A_{i} eq 0$，令$t=A_{i}$，然后置$A_{i}=0$，最后令$i$位置后的连续$t$个位置分别加1。这个是循环的，$n-1$之后是位置$0$。可能有些位置最后增加的值会超过1；（2）选择一个$i,0leq i <n$且$A_{i} eq 0$，然后从$i$开始(包括$i$)向前，每个位置的数字减去1，直到一个位置是$0$，然后把刚刚减去的值的和加到这个位置上。
可以看出操作（2）是操作（1）的逆操作。可以先将$A$只使用操作（1）变成除了$A_{0}$外其余位置都是0，$B$也这样操作，操作序列分别为$P,Q$，那么$P$加上$Q$的逆操作就是答案。
problem2 link
https://blog.csdn.net/xyyxyyx/article/details/102505744#antiNim_41
http://makaidong.com/Saurus/18221_5909731.html
(1)全是1(不包含魔力堆):
如果全是1，那么无论有几堆，先手都是必胜的. 因为如果有奇数个1，那么Alice直接拿掉魔力石子，然后选择改变游戏，那么他还是赢的．如果有偶数个1，那么Alice直接拿掉魔力石子，然后不选择改变游戏，于是他还是赢的。
(2)不全是1:
anti-nim的先手必胜条件（不考虑多魔法石子):
i SG为0，且所有石子均为1
ii SG不为0，且存在一堆石子大于1
所以，如果不全是1，且SG为0的话，Alice是必输的，因为他取魔力石子后，仍然无法改变必输的情况
所以现在情况只有不全是1，且SG不为0. 注意到这个时候任何一方如果直接取魔力石子，都是必败的.所以双方应该会保持SG不为0，然后进行对峙
首先考虑所以石子的数量不超过3.那么SG函数的值就只有3个，1,2,3. 当SG为1或3的时候，肯定有一种取法使得SG为2. 而SG为2的最终情况是2附加一个魔力石子，这种情况是必败的. 所以当石子的数量不超过3时，SG=2先手必败，反之必胜
接下来考虑石子的数量超过3，也就是有4和4以上的数.那么SG函数的值可以分成1和超过1的那些情况. 如果当前SG值为1，那么只能把它变成超过1的值，然而对手又可以把它变回到1
我们考虑假设只有1个超过3的数，那么这时候SG值肯定是大于3的. 直接改变这个数，我们可以使得接下来的局面变成SG=2. 也就是说，如果只有1个超过3的数，那么就是先手必胜
那么如果SG值为1，且我们知道存在超过3的数，那么超过3的数的数量必定至少有2个. 也就是说，经过不断地对峙，原来SG值为1的话，现在SG值仍然为1. 但是经过了很多减少，一定会达到这个局面. 即SG值为1，且超过3的数量只有2个
当这2个其中的一个数减到4以下时，就变成了只有1个超过3的数, 即SG->1->3->2（最终结果）.也就是说SG如果为1，必定会转化成2，那么SG=1就是必败局面，而其他情况是必胜局面
最后结论就是: 如果有大于3的数，那么SG=1必败; 如果没有，那么SG=2必败
problem3 link
令$T=frac{m(m-1)}{2}$．表示有 這麼多個二元組$(i,j), 0leq i<j<m$
計算這樣一個大小爲$2^T$的數組，$f[0],f[1],.., f[2^{T}-1]$．其中$f[i]$表示在一維空間中選出$m$個區間，使得$i$中爲１的那些bit對應的二元組相交的情況有多少種．
每一個區間看作一對匹配的括號．首先枚舉有多少種不同的括號（不同的兩個不完全重合）.
比如對於2種不同括號的有五種形狀：
egin{matrix}
( & &) & & (& &) & & (& & &) & & (&) & & ( &) & & \
& (& &) & & (&) & & & (&) & & & & (&) & (& &) &
end{matrix}
前後兩個滿足$L_{1}<L_{2}$或者$L_{1}<=L_{2}, R_{1}<R_{2}$， 以避免重復搜索
然後對於$m$個區間枚舉每個區間屬於哪一種種類的括號．
有了這個$f$數組之後， 對於$k$維的問題，就是求解$f_{new}[i]=sum_{j&k=i}f_{old}[j]f_{old}[k]$這樣一個dp, 重復計算$k$次就行． 這個可以用Fast Walsh Hadamard.
https://codeforces.com/blog/entry/50572
https://blog.csdn.net/zxyoi_dreamer/article/details/100515338
https://www.cnblogs.com/y-clever/p/6875743.html
https://www.bbsmax.com/A/qVdewO1QJP/
code for problem1
#include <vector>
class ReverseMancala {
public:
std::vector<int> findMoves(const std::vector<int> &S,
const std::vector<int> &T) {
auto p = get(S, false);
auto q = get(T, true);
std::copy(q.rbegin(), q.rend(), std::back_inserter(p));
return p;
}
private:
std::vector<int> get(std::vector<int> s, bool tag) {
int sum = 0;
int n = static_cast<int>(s.size());
for (int i = 0; i < n; ++i) {
sum += s[i];
}
std::vector<int> ans;
while (s[0] != sum) {
int p = 1;
while (!s[p]) {
++p;
}
if (!tag) {
ans.push_back(p);
} else {
ans.push_back((p + s[p]) % n + n);
}
int cur = s[p];
s[p] = 0;
for (int i = 0; i < cur; ++i) {
++s[(p + 1 + i) % n];
}
}
return ans;
}
};
code for problem2
#include <algorithm>
#include <string>
#include <vector>
class MagicNim {
public:
std::string findWinner(const std::vector<int> &a) {
int sg = 0;
int m = 0;
for (int x : a) {
sg ^= x;
m = std::max(m, x);
}
if (m >= 4) {
return sg == 1 ? "Bob" : "Alice";
} else {
return sg == 2 ? "Bob" : "Alice";
}
}
};
code for problem3
#include <vector>
class Hyperboxes {
public:
int findCount(int n, int m, int k) {
this->m = m;
c.resize(m * 2 + 1);
c[0] = 1;
for (int i = 1; i <= m * 2; ++i) {
c[i] = Mul(c[i - 1], n - i + 1);
c[i] = Mul(c[i], Pow(i, kMod - 2));
}
int total = m * (m - 1) / 2;
int S = 1 << total;
g.resize(S, 0);
f.resize(S, 0);
for (int cur = 1; cur <= m; ++cur) {
for (auto &e : g) {
e = 0;
}
std::vector<int> visited(m, 0);
std::vector<std::pair<int, int>> group_and_pos(m * 2);
std::vector<int> group(m);
Dfs1(0, -1, cur, &group_and_pos, 0);
Dfs2(0, cur, &group, &visited);
}
for (int i = 1; i < S; i <<= 1) {
for (int j = 0; j < S; j += i << 1) {
for (int k = 0; k < i; ++k) {
f[j + k] = Add(f[j + k], f[i + j + k]);
}
}
}
for (int i = 0; i < S; ++i) {
f[i] = Pow(f[i], k);
}
for (int i = 1; i < S; i <<= 1) {
for (int j = 0; j < S; j += i << 1) {
for (int k = 0; k < i; ++k) {
f[j + k] = Sub(f[j + k], f[i + j + k]);
}
}
}
return f[0];
}
private:
int Index(int i, int j, int m) {
if (i > j) {
std::swap(i, j);
}
int pre = i == 0 ? 0 : (m - 1 + m - i) * i / 2;
return pre + (j - i - 1);
}
int Add(int a, int b) {
a += b;
if (a >= kMod) {
a -= kMod;
}
return a;
}
int Sub(int a, int b) {
a -= b;
if (a < 0) {
a += kMod;
}
return a;
}
int Mul(int a, int b) {
long long la = a;
return static_cast<int>(la * b % kMod);
}
int Pow(int a, int b) {
long long la = a;
long long r = 1;
while (b > 0) {
if ((b & 1) == 1) {
r = r * la % kMod;
}
la = la * la % kMod;
b >>= 1;
}
return static_cast<int>(r);
}
void Dfs1(int cur, int gcnt, int gnum,
std::vector<std::pair<int, int>> *group, int mask) {
if (cur == 2 * gnum) {
std::vector<int> left(m);
std::vector<int> right(m);
for (int i = 0; i < 2 * gnum; ++i) {
const auto &e = group->at(i);
if (e.first < gnum) {
left[e.first] = e.second;
} else {
right[e.first - gnum] = e.second;
}
}
for (int i = 0; i < gnum; ++i) {
if (left[i] == right[i]) {
return;
}
}
for (int i = 0; i < gnum; ++i) {
for (int j = i + 1; j < gnum; ++j) {
if (left[i] == left[j] && right[i] >= right[j]) {
return;
}
}
}
int st = 0;
for (int i = 0; i < gnum; ++i)
for (int j = i + 1; j < gnum; ++j)
if (right[i] >= left[j]) st |= 1 << Index(i, j, gnum);
g[st] = Add(g[st], c[gcnt + 1]);
return;
}
auto &e = group->at(cur);
for (int i = 0; i < gnum; ++i) {
if ((mask & (1 << i)) != 0) {
continue;
}
e.first = i;
mask |= 1 << i;
e.second = gcnt + 1;
Dfs1(cur + 1, gcnt + 1, gnum, group, mask);
if (cur && e.first > group->at(cur - 1).first) {
e.second = gcnt;
Dfs1(cur + 1, gcnt, gnum, group, mask);
}
mask ^= 1 << i;
break;
}
for (int i = 0; i < gnum; ++i) {
if ((mask & (1 << i)) != 0 && (mask & (1 << (i + gnum))) == 0) {
e.first = i + gnum;
mask |= 1 << (i + gnum);
e.second = gcnt + 1;
Dfs1(cur + 1, gcnt + 1, gnum, group, mask);
if (cur && e.first > group->at(cur - 1).first) {
e.second = gcnt;
Dfs1(cur + 1, gcnt, gnum, group, mask);
}
mask ^= 1 << (i + gnum);
}
}
}
void Dfs2(int cur, int gnum, std::vector<int> *group,
std::vector<int> *visited) {
if (cur == m) {
for (int i = 0; i < gnum; ++i) {
if (visited->at(i) == 0) {
return;
}
}
int total = gnum * (gnum - 1) / 2;
for (int s = 0; s < (1 << total); ++s) {
if (g[s] == 0) {
continue;
}
int st = 0;
for (int i = 0; i < m; ++i) {
for (int j = i + 1; j < m; ++j) {
if (group->at(i) == group->at(j) ||
(s & (1 << Index(group->at(i), group->at(j), gnum)))) {
st |= 1 << Index(i, j, m);
}
}
}
f[st] = Add(f[st], g[s]);
}
return;
}
for (int j = 0; j < gnum; ++j) {
group->at(cur) = j;
visited->at(j) += 1;
Dfs2(cur + 1, gnum, group, visited);
visited->at(j) -= 1;
}
}
static constexpr int kMod = 998244353;
int m;
std::vector<int> c;
std::vector<int> g;
std::vector<int> f;
};