A. 多项式
推柿子：
\[\begin{aligned} &\sum\limits_{k = 0}^{n}b_{k}(x - t)^{k}\\ =&\sum\limits_{k = 0}^{n}b_{k}\sum\limits_{i = 0}^{k}\binom{k}{i}x^{i}(-t)^{k-i}\\ =&\sum\limits_{0 \leqslant i \leqslant k \leqslant n}\binom{k}{i}b_{k}(-t)^{k - i}x^{i} \end{aligned} \]因为相同次数的项系数相同，所以：
\[a_{i} = \sum\limits_{k = i}^{n}\binom{k}{i}b_{k}(-t)^{k - i} \]二项式反演算是二项式的必备技能很合理吧，所以反演一下就有：
\[b_{k} = \sum\limits_{i = k}^{n}\binom{i}{k}a_{i}t^{i - k} \]什么，\(n\) 和 \(m\) 都太大了？\(\binom{i}{k}\) 不好算？\(\binom{i}{k} = \binom{i}{i - k}\)。
不想写高精度？去学 python 得了。
代码（我的高精度在主函数里面，但确实短）：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
basic_string<ll> n, m, mul = {1}, ans, tmp, mu;
string s;
int pos, sub, t, x, r, len, now, p, a[3388];
void del0(basic_string<ll>& s) {
while(!s.empty() && !s.back()) s.pop_back();
if(s.empty()) s = {0};
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
a[0] = 1;
for(int i = 1; i < 3388; ++i) a[i] = (a[i - 1] * 1234ll + 5678) % 3389;
cin >> s;
for(const auto& i : s) n.push_back(i - '0');
cin >> t >> s;
for(const auto& i : s) m.push_back(i - '0'), pos = (pos * 10 + m.back()) % 3388;
sub = (n.back() + 10 - m.back()) % 10;
reverse(n.begin(), n.end()), reverse(m.begin(), m.end());
for(int moew = 0; moew <= sub; ++moew, pos = (pos + 1) % 3388) {
tmp = {0};
for(const auto& i : mul) tmp.back() += i * a[pos], r = tmp.back() / 10, tmp.back() %= 10, tmp.push_back(r);
while(tmp.back() >= 10) r = tmp.back() / 10, tmp.back() %= 10, tmp.push_back(r);
len = max(ans.length(), tmp.length()), ans.resize(len + 1), tmp.resize(len + 1);
for(int i = 0; i < len; ++i) ans[i] += tmp[i], r = ans[i] / 10, ans[i] %= 10, ans[i + 1] += r;
r = 1; for(auto& i : m) i += r, r = i / 10, i %= 10; m.push_back(r);
mu = {0};
for(const auto& i : m) mu.back() += i * t, r = mu.back() / 10, mu.back() %= 10, mu.push_back(r);
while(mu.back() >= 10) r = mu.back() / 10, mu.back() %= 10, mu.push_back(r);
tmp.assign(mul.length() + mu.length() + 5, 0), now = 0;
for(const auto& i : mul) {
p = now;
for(const auto& j : mu) tmp[p] += i * j, r = tmp[p] / 10, tmp[p] %= 10, tmp[p + 1] += r, ++p;
++now;
}
del0(tmp);
while(tmp.back() >= 10) r = tmp.back() / 10, tmp.back() %= 10, tmp.push_back(r);
reverse(tmp.begin(), tmp.end());
r = 0, mul.clear();
for(const auto& i : tmp) r = r * 10 + i, mul.push_back(r / (moew + 1)), r %= moew + 1;
reverse(mul.begin(), mul.end());
}
del0(ans);
reverse(ans.begin(), ans.end());
for(const auto& i : ans) cout << i;
return 0;
}
B. A Very Simple Problem
怎么办怎么办看不出来哪里有二项式？
于是我尝试拉插。然后失败了。
那就研究一下通项公式或者递推公式。
如何从第 \(i\) 项推出 \(i + 1\) 项？直接展开：
\[\begin{aligned} &(i + 1)^{x}x^{i + 1}\\ =&x\sum\limits_{j = 0}^{x}\binom{x}{j}i^{j}x^{i}\\ \end{aligned} \]发现 \(x\) 的范围非常小！懒得继续推什么式子直接给丢进矩阵里加速，矩阵多开一个 \(sum\) 的位置即可。
矩阵大概长这样：
\[\begin{bmatrix} i^{0}x^{i} & i^{1}x^{i} & \cdots & i^{x}x^{i} & sum \end{bmatrix} \times \texttt{转移矩阵} =\begin{bmatrix} (i + 1)^{0}x^{i + 1} & (i + 1)^{1}x^{i + 1} & \cdots & (i + 1)^{x}x^{i + 1} & sum \end{bmatrix} \]（因为转移矩阵太大了就给放下面来了）
\[\begin{bmatrix} 1k & 1k & 1k & 1k & \cdots & \binom{x}{0}k & 0\\ 0 & 1k & 2k & 3k & \cdots & \binom{x}{1}k & 0\\ 0 & 0 & 1k & 3k & \cdots & \binom{x}{2}k & 0\\ 0 & 0 & 0 & 1k & \cdots & \binom{x}{3}k & 0\\ \vdots & \vdots & \vdots& \vdots& \ddots & \vdots\\ 0 & 0 & 0 & 0 & \cdots & \binom{x}{x}k & 1\\ 0 & 0 & 0 & 0 & \cdots & 0 & 1\\ \end{bmatrix} \]最后一列是给 \(sum\) 转移的。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, x, siz = 52, mod = 998244353;
struct modint {
int x;
modint(ll v = 0): x((v % mod + mod) % mod) {}
friend modint operator + (const modint& x, const modint& y) {return (ll)x.x + y.x >= mod ? (ll)x.x + y.x - mod : x.x + y.x;}
friend modint operator * (const modint& x, const modint& y) {return (ll)x.x * y.x % mod;}
modint operator = (const modint& _) {x = _.x; return *this;}
modint operator += (const modint& _) {*this = *this + _; return *this;}
friend ostream& operator << (ostream& out, const modint& _) {return out << _.x;}
} res;
struct matrix {
modint val[52][52];
matrix(modint v = 0) {
for(int i = 0; i < siz; ++i) {
for(int j = 0; j < siz; ++j) {
val[i][j] = (i == j ? v : 0);
}
}
}
void operator *= (const matrix& _) {
static matrix res;
for(int i = 0; i < siz; ++i) {
for(int j = 0; j < siz; ++j) {
res.val[i][j] = 0;
for(int k = 0; k < siz; ++k) {
res.val[i][j] += val[i][k] * _.val[k][j];
}
}
}
*this = res;
}
} a, ans;
matrix ksm(matrix& x, ll y) {
matrix ret(1);
while(y) {
if(y & 1) ret *= x;
x *= x, y >>= 1;
}
return ret;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
while(cin >> n >> x >> mod) {
if(!(~n) && !(~x) && !(~mod)) break;
siz = x + 2;
for(int i = 0; i <= x; ++i) {
a.val[0][i] = x;
for(int j = 1; j <= i; ++j) {
a.val[j][i] = a.val[j - 1][i - 1] + a.val[j][i - 1];
}
for(int j = i + 1; j < siz; ++j) a.val[j][i] = 0;
}
for(int i = 0; i < siz; ++i) a.val[i][x + 1] = 0;
a.val[x][x + 1] = a.val[x + 1][x + 1] = 1;
ans = ksm(a, n);
res = 0;
for(int i = 0; i <= x; ++i) res += x * ans.val[i][x + 1];
cout << res << '\n';
}
return 0;
}
C. Height All the Same
目标为「推平」，那肯定就和高度无关。
并且每次都放两个方块，那么只考虑每个位置的奇偶性即可（或者说模 \(2\) 意义下的高度，下面直接以模 \(2\) 意义下的高度来讨论）。
操作二不会改变高度，故忽略。
然后分两个小情况：
- \(n \times m\) 为奇数，那么什么初始局面都可以。
此时要么有偶数个 \(0\)，要么有偶数个 \(1\)，那么对着偶数的那一部分进行操作一即可，如果没有相邻的，那么随便找一对相邻的 \(1\) 和 \(0\) 进行操作一，就可以让它们「交换」。
- \(n \times m\) 为偶数，\(0\) 和 \(1\) 的数量同时为偶数即可。
必要性不用证明了，充分性考虑反证法。
如果 \(0\) 和 \(1\) 的数量同时为奇数，操作可以使得 \(0/1\) 的数量 \(\pm 2\)，但因为它们的数量都是奇数，操作后仍为奇数，始终无法推平，所以奇数的情况不可行。
那么此时答案就是：
\[\sum\limits_{i = 0}^{\frac{nm}{2}}\binom{nm}{2i}oddcnt^{2i}evencnt^{nm - 2i} \]没法使用二项式定理，难受，直接补全！
\[\sum\limits_{i = 0}^{\frac{nm}{2}}\binom{nm}{2i}oddcnt^{2i}evencnt^{nm - 2i} + \sum\limits_{i = 1}^{\frac{nm}{2}}\binom{nm}{2i - 1}oddcnt^{2i - 1}evencnt^{nm - 2i + 1} \]它等于 \((oddcnt + evencnt)^{nm}\)。
怎么把多出来的项消掉？发现 \((-1)^{2i} = 1, (-1)^{2i - 1} = -1\)，尝试丢进去：
\[\sum\limits_{i = 0}^{\frac{nm}{2}}\binom{nm}{2i}(-oddcnt)^{2i}evencnt^{nm - 2i} + \sum\limits_{i = 1}^{\frac{nm}{2}}\binom{nm}{2i - 1}(-oddcnt)^{2i - 1}evencnt^{nm - 2i + 1} \]它等于 \((evencnt - oddcnt)^{nm} = (oddcnt - evencnt)^{nm}\)（\(nm\) 为偶数）。
而答案就是 \(\dfrac{(oddcnt + evencnt)^{nm} + (oddcnt - evencnt)^{nm}}{2}\)。
随便怎么算都行啦。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int mod = 998244353;
struct modint {
int x;
modint(ll v = 0): x((v % mod + mod) % mod) {}
friend modint ksm(modint x, ll y) {
modint ret = 1;
while(y) {if(y & 1) ret *= x; x *= x, y >>= 1;}
return ret;
}
friend modint operator + (const modint& x, const modint& y) {return x.x + y.x >= mod ? x.x + y.x - mod : x.x + y.x;}
friend modint operator - (const modint& x, const modint& y) {return x.x < y.x ? x.x - y.x + mod : x.x - y.x;}
friend modint operator * (const modint& x, const modint& y) {return (ll)x.x * y.x % mod;}
friend modint operator / (const modint& x, const modint& y) {return x * ksm(y, mod - 2);}
modint operator = (const modint& _) {x = _.x; return *this;}
modint operator += (const modint& _) {*this = *this + _; return *this;}
modint operator -= (const modint& _) {*this = *this - _; return *this;}
modint operator *= (const modint& _) {*this = *this * _; return *this;}
modint operator /= (const modint& _) {*this = *this / _; return *this;}
bool operator == (const modint& _) const {return x == _.x;}
bool operator != (const modint& _) const {return x != _.x;}
friend istream& operator >> (istream& in, modint& _) {static ll tmp; return in >> tmp; _.x = tmp % mod;}
friend ostream& operator << (ostream& out, const modint& _) {return out << _.x;}
};
ll n, m, l, r;
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m >> l >> r;
if((n * m) & 1) {
cout << ksm(modint(r - l + 1), n * m);
return 0;
}
cout << (ksm(modint(r - l + 1), n * m) + ksm(modint((r & 1) - ((l - 1) & 1)), n * m)) / 2;
return 0;
}
D. Binomial Coefficient is Fun
智力讲过了，不写了，贴一个洛谷题解区敷衍一下表示一下。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int mod = 1000000007;
struct modint {
int x;
modint(ll v = 0): x((v % mod + mod) % mod) {}
friend modint ksm(modint x, ll y) {
modint ret = 1;
while(y) {if(y & 1) ret *= x; x *= x, y >>= 1;}
return ret;
}
friend modint operator + (const modint& x, const modint& y) {return x.x + y.x >= mod ? x.x + y.x - mod : x.x + y.x;}
friend modint operator - (const modint& x, const modint& y) {return x.x < y.x ? x.x - y.x + mod : x.x - y.x;}
friend modint operator * (const modint& x, const modint& y) {return (ll)x.x * y.x % mod;}
friend modint operator / (const modint& x, const modint& y) {return x * ksm(y, mod - 2);}
modint operator = (const modint& _) {x = _.x; return *this;}
modint operator += (const modint& _) {*this = *this + _; return *this;}
modint operator -= (const modint& _) {*this = *this - _; return *this;}
modint operator *= (const modint& _) {*this = *this * _; return *this;}
modint operator /= (const modint& _) {*this = *this / _; return *this;}
bool operator == (const modint& _) const {return x == _.x;}
bool operator != (const modint& _) const {return x != _.x;}
friend istream& operator >> (istream& in, modint& _) {static ll tmp; in >> tmp; _.x = tmp % mod; return in;}
friend ostream& operator << (ostream& out, const modint& _) {return out << _.x;}
};
int n, a, sum;
modint m, num = 1, den = 1;
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
cin >> a;
sum += a;
}
sum += n;
m += n;
for(int i = 1; i <= sum; ++i) {
num *= m - i + 1;
den *= i;
}
cout << num / den;
return 0;
}
E. Anton and School - 2
什么什么蒙德卷积的板板。
钦定选择的最后一个 \(\texttt{(}\)，令 \(pre_{i}\) 表示 \(1 \sim i\) 中有多少 \(\texttt{(}\)，\(suf_{i}\) 表示 \(i \sim n\) 中有多少 \(\texttt{)}\)（\(n\) 为字符串长度）。
答案就是：
\[\sum\limits_{1 \leqslant i \leqslant n \land s_{i} = \texttt{(}}\sum\limits_{j = 1}^{\min{pre_{i}, suf_{i}}}\binom{pre_{i} - 1}{j - 1}\binom{suf_{i}}{j} \]后面那一部分直接什么什么蒙德卷积就好了。
变成：
\[\sum\limits_{1 \leqslant i \leqslant n \land s_{i} = \texttt{(}}\binom{pre_{i} +suf_{i} - 1}{pre_{i}} \]代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int mod = 1000000007;
int n, pre[200005], suf[200005];
string s;
struct modint {
int x;
modint(ll v = 0): x((v % mod + mod) % mod) {}
friend modint ksm(modint x, ll y) {
modint ret = 1;
while(y) {if(y & 1) ret *= x; x *= x, y >>= 1;}
return ret;
}
friend modint operator + (const modint& x, const modint& y) {return x.x + y.x >= mod ? x.x + y.x - mod : x.x + y.x;}
friend modint operator - (const modint& x, const modint& y) {return x.x < y.x ? x.x - y.x + mod : x.x - y.x;}
friend modint operator * (const modint& x, const modint& y) {return (ll)x.x * y.x % mod;}
friend modint operator / (const modint& x, const modint& y) {return x * ksm(y, mod - 2);}
modint operator = (const modint& _) {x = _.x; return *this;}
modint operator += (const modint& _) {*this = *this + _; return *this;}
modint operator -= (const modint& _) {*this = *this - _; return *this;}
modint operator *= (const modint& _) {*this = *this * _; return *this;}
modint operator /= (const modint& _) {*this = *this / _; return *this;}
bool operator == (const modint& _) const {return x == _.x;}
bool operator != (const modint& _) const {return x != _.x;}
friend istream& operator >> (istream& in, modint& _) {static ll tmp; return in >> tmp; _.x = tmp % mod;}
friend ostream& operator << (ostream& out, const modint& _) {return out << _.x;}
};
modint ans, fct[200005], inv[200005];
modint c(int n, int m) {
if(m > n) return 0;
return fct[n] * inv[m] * inv[n - m];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
fct[0] = 1;
for(int i = 1; i <= 200000; ++i) fct[i] = fct[i - 1] * i;
inv[200000] = 1 / fct[200000];
for(int i = 200000; i >= 1; --i) inv[i - 1] = inv[i] * i;
cin >> s;
n = s.length();
s = "V" + s;
for(int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + (s[i] == '(');
for(int i = n; i >= 1; --i) suf[i] = suf[i + 1] + (s[i] == ')');
for(int i = 1; i <= n; ++i) {
if(s[i] == '(') {
ans += c(pre[i] + suf[i] - 1, pre[i]);
}
}
cout << ans;
return 0;
}