problem1 link
直接动态规划即可。
problem2 link
假设有$r$行,$c$列被修改了奇数次，那么一定有$r*W+c*H-2*r*c=S$。可以枚举这样的组合$(r,c)$，然后计算答案。比如对于$r$行来说，首先需要从$H$行中选出$r$行，即$C_{H}^{r}$。然后对于剩下的$Rcount-r$（一定是偶数）次修改。令$t=\frac{Rcount-r}{2}$，那么就是求有多少个$H$元组 $(a_{1},a_{2},..,a_{H})$满足$a_{i} \ge 0$且$\sum_{i=1}^{H}a_{i}=K$，运用隔板法，这个答案为 $C_{K+H-1}^{H-1}$。
problem3 link
首先，枚举初始时Head所在的位置，然后可以计算出哪些位置是可以随便放置的（因为最后会被修改）。最后，对所有的情况进行容斥。
code for problem1
#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_set>
#include <vector> class CuttingBitString {
public:
int getmin(std::string S) {
const int N = static_cast<int>(S.size());
std::unordered_set<std::string> all;
long long current = 1L;
while (true) {
std::string s = GetBinary(current);
if (s.size() > S.size()) {
break;
}
all.insert(s);
current *= 5;
} auto Check = [&](int left, int right) {
return all.find(S.substr(left - 1, right - left + 1)) != all.end();
}; std::vector<int> f(N + 1, -1);
f[0] = 0;
for (int i = 1; i <= N; ++i) {
for (int j = 0; j < i; ++j) {
if (f[j] != -1 && Check(j + 1, i)) {
int t = f[j] + 1;
if (f[i] == -1 || f[i] > t) {
f[i] = t;
}
}
}
}
return f[N];
} private:
std::string GetBinary(long long x) {
std::string s = "";
while (x != 0) {
if (x % 2 == 0) {
s += '0';
} else {
s += '1';
}
x >>= 1;
}
std::reverse(s.begin(), s.end());
return s;
}
};
code for problem2
#include <algorithm>
#include <iostream>
#include <vector> const int MAX_N = 2332;
const int MAX_M = 1555; int binomial[MAX_N + 1][MAX_M + 1]; class XorBoard {
static constexpr int mod = 555555555; public:
int count(int H, int W, int Rcount, int Ccount, int S) {
Initialize(std::max(Rcount, Ccount) / 2 + std::max(H, W), std::max(H, W)); auto Compute = [&](int H, int Rcount, int h) -> long long {
int t = (Rcount - h) >> 1;
return static_cast<long long>(binomial[H][h]) *
static_cast<long long>(binomial[t + H - 1][H - 1]) % mod;
}; int result = 0;
int start_row = Rcount & 1;
int start_col = Ccount & 1;
for (int i = start_row; i <= Rcount && i <= H; i += 2) {
long long part1 = Compute(H, Rcount, i);
for (int j = start_col; j <= Ccount && j <= W; j += 2) {
if (i * W + j * H - i * j * 2 != S) {
continue;
}
long long part2 = Compute(W, Ccount, j);
result += static_cast<int>(part1 * part2 % mod);
if (result >= mod) {
result -= mod;
}
}
}
return result;
} private:
void Initialize(int max_n, int max_m) {
binomial[0][0] = 1;
for (int i = 1; i <= max_n; ++i) {
binomial[i][0] = 1;
binomial[i][1] = i;
for (int j = 2; j <= max_m; ++j) {
binomial[i][j] = binomial[i - 1][j - 1] + binomial[i - 1][j];
if (binomial[i][j] >= mod) {
binomial[i][j] -= mod;
}
}
}
}
};
code for problem3
#include <iostream>
#include <string>
#include <unordered_set>
#include <vector> class MapGuessing {
public:
long long countPatterns(std::string goal, std::vector<std::string> code) {
std::string cmd = "";
for (auto &e : code) {
cmd += e;
}
std::unordered_set<long long> all_states;
const int N = static_cast<int>(goal.size());
for (int i = 0; i < N; ++i) {
std::vector<int> types(N, -1);
int head = i;
long long state = 0;
bool tag = true;
for (size_t j = 0; j < cmd.size(); ++j) {
if (cmd[j] == '<') {
--head;
} else if (cmd[j] == '>') {
++head;
} else if (cmd[j] == '0') {
types[head] = 0;
} else {
types[head] = 1;
}
if (head < 0 || head >= N) {
tag = false;
break;
}
bool ok = true;
for (int j = 0; j < N && ok; ++j) {
if (types[j] != -1 && types[j] + '0' != goal[j]) {
ok = false;
}
}
if (ok) {
for (int j = 0; j < N && ok; ++j) {
if (types[j] != -1) {
state |= 1LL << j;
}
}
}
}
if (tag) {
all_states.insert(state);
}
}
std::vector<long long> all;
for (auto e : all_states) {
all.push_back(e);
}
return Dfs(all, 0, (1LL << N) - 1, 0);
} private:
long long Dfs(const std::vector<long long> &all_states, size_t depth,
long long current_state, int sgn) {
if (depth == all_states.size()) {
return sgn * Count(current_state);
}
if (current_state == 0) {
return 0;
}
return Dfs(all_states, depth + 1, current_state, sgn) +
Dfs(all_states, depth + 1, current_state & all_states[depth],
sgn <= 0 ? 1 : -1);
} long long Count(long long s) {
int t = 0;
while (s != 0) {
t += s & 1;
s >>= 1;
}
return 1LL << t;
}
};