\(0+100+40+0=140\)，怎么都会 T3 啊
#A. char
令 \(dp_{i,j}\) 为已经考虑了文本串前 \(i\) 位且将所有 * 填入了字符，匹配了模式串的前 \(j\) 位的方案总数
转移显然，若第 \(i\) 位不是 *，则只有这一位和模式串相等才会有答案，即 \(dp_{i,j}=\begin{cases}dp_{i-1,j-1} & s_i=t_k\\0 & \text{else}\end{cases}\)
否则当前位可以填任意字符，则 \(dp_{i,j}=\sum dp_{i-1,j}\)
// BLuemoon_
#include <bits/stdc++.h>using namespace std;
using LL = long long;const int kMaxM = 1e3 + 5, kMaxN = 5e4 + 5;
const int kP = 998244853;int n, m, sz[kMaxN];
LL dp[kMaxN][kMaxM], pre[kMaxN][kMaxM], ans;
string s, t[kMaxN];int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);freopen("char.in", "r", stdin), freopen("char.out", "w", stdout);cin >> n >> m >> s;for (int i = 1; i <= m; i++) {cin >> t[i], sz[i] = t[i].size();for (int j = 1; j <= n; j++) {fill(dp[j], dp[j] + sz[i] + 2, 0), fill(pre[j], pre[j] + sz[i] + 2, 0);if (s[j - 1] != '*') {for (int k = 1; k <= sz[i]; k++) {if (s[j - 1] == t[i][k - 1]) {(dp[j][k] += dp[j - 1][k - 1] + (k == 1)) %= kP;}pre[j][k] = pre[j][k - 1] + dp[j][k] % kP;}} else {dp[j][0] = dp[j - 1][0] + 1;for (int k = 1; k <= sz[i]; k++) {(dp[j][k] += (dp[j - 1][0] + pre[j - 1][k] + 1) % kP) %= kP;pre[j][k] = pre[j][k - 1] + dp[j][k] % kP;}}}for (int j = 1; j <= n; j++) {(ans += dp[j][sz[i]]) %= kP;}}cout << ans << '\n';return 0;
}
#B. tree
感觉很像原题啊找到原题了
引入那个 T2 的概念：影响域
由于最多改变一个颜色且 \(n \le 3000\)，可以想到枚举修改的点
对于每条边，求出其左右两边的影响域，答案即为左边白点乘右边黑点加左边黑点乘右边白点，枚举修改的点，对于每条边修改影响域中黑白点的数量，直接计算比大小即可
// BLuemoon_
#include <bits/stdc++.h>using namespace std;
using LL = long long;const int kMaxN = 3e3 + 5;vector<pair<int, LL>> g[kMaxN];
int n, c[kMaxN], u[kMaxN], v[kMaxN];
LL ans = 1e18, calc, cnt1[2][kMaxN], cnt2[2][kMaxN], w[kMaxN]; // cnt1 : white cnt2 : black
unordered_map<int, bool> mp[2][kMaxN];void DFS(int u, int fa, LL lt, int ae, bool flag) {(c[u] == 0 ? cnt1[flag][ae] : cnt2[flag][ae])++, mp[flag][ae][u] = 1;for (pair<int, LL> i : g[u]) {int v = i.first;LL w = i.second;if (v != fa) {if (w < lt) {DFS(v, u, lt, ae, flag);}}}
}
LL Calc(int x, LL ret = calc) {for (int i = 1; i < n; i++) {if (mp[0][i].count(x)) {ret -= w[i] * (cnt1[0][i] * cnt2[1][i] + cnt1[1][i] * cnt2[0][i]);(c[x] == 1) ? (cnt1[0][i]++, cnt2[0][i]--) : (cnt1[0][i]--, cnt2[0][i]++);ret += w[i] * (cnt1[0][i] * cnt2[1][i] + cnt1[1][i] * cnt2[0][i]);(c[x] == 1) ? (cnt1[0][i]--, cnt2[0][i]++) : (cnt1[0][i]++, cnt2[0][i]--);} else if (mp[1][i].count(x)) {ret -= w[i] * (cnt1[0][i] * cnt2[1][i] + cnt1[1][i] * cnt2[0][i]);(c[x] == 1) ? (cnt1[1][i]++, cnt2[1][i]--) : (cnt1[1][i]--, cnt2[1][i]++);ret += w[i] * (cnt1[0][i] * cnt2[1][i] + cnt1[1][i] * cnt2[0][i]);(c[x] == 1) ? (cnt1[1][i]--, cnt2[1][i]++) : (cnt1[1][i]++, cnt2[1][i]--);}}return ret;
}int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);freopen("tree.in", "r", stdin), freopen("tree.out", "w", stdout);cin >> n;for (int i = 1; i <= n; i++) {cin >> c[i];}for (int i = 1; i < n; i++) {cin >> u[i] >> v[i] >> w[i], g[u[i]].push_back({v[i], w[i]}), g[v[i]].push_back({u[i], w[i]});}for (int i = 1; i < n; i++) {DFS(u[i], v[i], w[i], i, 0), DFS(v[i], u[i], w[i], i, 1), calc += w[i] * (cnt1[0][i] * cnt2[1][i] + cnt1[1][i] * cnt2[0][i]);}ans = calc;for (int i = 1; i <= n; i++) {ans = max(ans, Calc(i));}cout << ans << '\n';return 0;
}
#C. wooden
考虑容斥，所有的情况为 \(\mathrm{C}_{\lceil\frac{x}{2}\rceil}^{3}\)
令选的长度为 \(x < u < v < w \le 4x\)，那么不满足条件的条件为 \(x+u \le v \le w-u \le 4x-u\)
先想 \(O(n)\) 做法，我们枚举 \(u\)，那么对于每一个 \(u\) 其他方案数为 \(\mathrm{C}_{3x-2u+1}^{2}\)，把这些式子拆开裂项合并就可以求出最终的式子：\(n^3-\frac{\lceil\frac{x}{2}\rceil\times (\lceil\frac{x}{2}\rceil+1)\times(2\lceil\frac{x}{2}\rceil+1)}{6}+[n\bmod 2=0]\times \lceil\frac{x}{2}\rceil^2\)
按照式子直接算即可
// BLuemoon_
#include <bits/stdc++.h>using namespace std;
using LL = long long;const LL kP = 1e9 + 7, iv = 166666668;LL n, ans, cnt, in;int main() {freopen("wooden.in", "r", stdin), freopen("wooden.out", "w", stdout);cin >> in, n = (in + 1) >> 1, n %= kP, ans = ((in * 3 % kP) * ((in * 3 % kP) - 1) % kP) * ((in * 3 % kP) - 2) % kP, (ans *= iv) %= kP;cnt = (((n % kP) * n % kP) * n % kP) - ((((n % kP) * ((n + 1) % kP) % kP) * ((n + n + 1) % kP) % kP) * iv % kP) % kP, (cnt += kP) %= kP;(in & 1 ^ 1) && ((cnt += (n % kP) * (n % kP) % kP) %= kP);cout << (((ans - cnt) % kP) + kP) % kP << '\n';return 0;
}
#D. stars
人机期望，以后再写
