董先生的休闲方案
( exttt{source: superguymj})
题意
有 (n) 张牌，每次随机选一张，如果选择的牌是当前没翻开的最小值，那么就翻开，否则合上并且记住这张牌是什么，问最后期望翻开的次数。
记期望耗时为 (displaystyle frac u v) ，其中 (u, v) 互素。若存在整数 (v^{-1}) ，满足 (vv^{-1} equiv 1 pmod {p^k}) ，则模 (p^k) 意义下的答案即为 (uv^{-1} pmod {p^k}) 。
对于 (100\%) 的数据,保证存在整数 (v^{-1}) ，(p) 为奇素数，且 (p le 10^5, np^k le 10^{18}) 。
题解
(f_i) 表示剩余 (i) 张牌未翻开的期望耗时，显然有
答案就是
问题就变成如何求
经典的调和级数，有什么高妙的推法呢？
注意虽然 (displaystyle frac 1 p mod {p^k}) 无定义，但是加起来 (ap) 个就可能存在定义。那么我们后面的地方要升上去一个 (p) 的幂。
直接实现是复杂度是 (mathcal O(n log n)) 的，考虑把前面那个式子进行变换。
后面那部分长度是 (n mod p < p) ，利用离线逆元即可线性处理。
然后我们考虑用广义二项式定理展开 ((jp + i)^{-1}) ，注意到 (displaystyle {-1 choose x} = (-1)^{x}) 即
还要注意到 (x ge k) 时 (p^x mod p^k) 为 (0) ，顺便交换一下和式
由于模数鬼畜，我们考虑用矩阵乘法求自然数幂和，要基于
这个组合递推式，可以预处理然后做到 (mathcal O(k^3 log n)) 。
那么最后的复杂度就是 (mathcal O((pk + k^3 log n) log n)) 的。
其实 ( exttt{min_25}) 博客 里有个 (mathcal O(sqrt p log p)) 求调和级数模 (p) 下的做法qwq
Mr. Kitayuta's Gift
( exttt{source: CF506E})
题意
给一个仅包含小写字母的字符串 (s) 。你需要选择恰好 (n) 个小写字母，并把他们分别插入到 (s) 的任意位置。问通过这种方式能生成出多少种回文串。
数据范围
(|s| le 200, n le 10^9)
题解
题目等价于，问有多少个长为 (|s| + n) 本质不同的回文串 (t) ，满足 (s) 为它的一个子序列。
首先不难想到一个很暴力的 (dp) ，令 (dp(i, l, r)) 为考虑完 (t) 的前后 (i) 个字符，然后还没有匹配上 (s_l sim s_r) 这一段。
转移的时候分 (s_l = s_r) 和 (s_l ot = s_r) 讨论，复杂度就是 (mathcal O(|s|^2 n)) 的。
然后发现其实是个常系数线性递推，用矩阵快速幂优化到 (mathcal O(|s|^6 log n)) 。
接下来的部分内容和 图，可以参考一下这篇 博客 。
然后考虑优化一下，不难发现其实我们就是问有多少个 (t) 的满足，能完全匹配上 (s) 这个特殊的序列自动机。
我们可以把 (s_l ot = s_r) 的称为 (n24) 类节点，(s_l = s_r) 的称为 (n25) 类节点。因为我们可以发现 (n24) 类节点有 (24) 个自环，(n25) 类节点有 (25) 个自环，注意一下结束节点 (q_0) 有 (26) 个自环，我们称其为 (n26) 类节点。
对于一条合法的自动机路径来说，设我们经过的不同的 (n24) 类节点个数为 (a) ，(n25) 类节点个数为 (b) ，那么显然有 (b = displaystyle lceil frac {|s| - a} 2 ceil) ，并且 (n24) 与 (n25) 类节点的先后顺序其实并不会影响我们的答案。
为什么呢？因为这样变化后的转移顺序虽然改变了，但是最后的每个系数的积并没有改变。
然后我们我们考虑设一个辅助 (dp) 为 (f(i, l, r)) 为当前未匹配的是 (s_l sim s_r) 经过 (i) 个 (n24) 类节点的方案数。
由于本质不同的 ((a, b)) 序列只有 (mathcal O(|s|)) 个，那么复杂度就优化成 (mathcal O(|s|^4 log n)) 了。但仍然还过不去。。。
然后考虑继续优化，我们其实可以把这 (mathcal O(|s|)) 个串的自动机一起建，怎么搞呢？
我们一开始先搞 (mathcal O(|s|)) 个 (n24) 类节点顺次相连，然后后面接 (mathcal O(|S|)) 个 (n25) 类节点，对于每个 (n25) 类节点下面接一个 (n26) 类节点。
这样的话，我们就可以做一遍矩阵快速幂，求出任意两个节点之间的方案数了。
然后我们可以枚举一开始经过的 (n24) 类点的数量，然后直接算答案就行了。
注意当 (|t|) 为奇数的时候会有些诡异，因为中心只有一个字符。考虑把不合法的减掉，就是最后一个中心匹配两个的时候，等价于倒数一步匹配剩下了的两个字符，这个减掉就好啦。
然后如果按拓扑序标号，那么只可能前面向后面连边，那么矩阵快速幂的时候枚举上三角就行了，乘上一个 (displaystyle frac 1 6) 的常数 233
复杂度就变成了 (mathcal O(|s|^3 + |s|^3 log n)) 。
可以考虑用 (mathcal {Cayley-Hamilton}) 优化到 (mathcal O(|s|^3 + |s|^2 log n)) 。。但是俺不会TAT
题解里还提到了 (mathcal O(|s|^3 + log n)) 的不需要矩阵的做法，但是是一个艰深的推式子做法，不优美且十分麻烦。。。
代码
#include <bits/stdc++.h>
#define For(i, l, r) for (register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for (register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Rep(i, r) for (register int i = (0), i##end = (int)(r); i < i##end; ++i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endl
using namespace std;
template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; }
inline int read() {
int x(0), sgn(1); char ch(getchar());
for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
return x * sgn;
}
void File() {
#ifdef zjp_shadow
freopen ("E.in", "r", stdin);
freopen ("E.out", "w", stdout);
#endif
}
const int N = 210, Mod = 10007;
int len;
struct Mat {
int a[N << 1][N << 1];
Mat() { Set(a, 0); }
void Unit() { For (i, 1, len) a[i][i] = 1; }
inline Mat friend operator * (const Mat &lhs, const Mat &rhs) {
Mat res;
For (i, 1, len) For (j, i, len) {
long long tmp = 0;
For (k, i, j) tmp += lhs.a[i][k] * rhs.a[k][j];
res.a[i][j] = tmp % Mod;
}
return res;
}
};
inline Mat fpm(Mat x, int power) {
Mat res; res.Unit();
for (; power; power >>= 1, x = x * x)
if (power & 1) res = res * x;
return res;
}
int f[N][N][N]; char S[N];
int Calc(int x, int l, int r) {
int &val = f[x][l][r];
if (~val) return val;
if (l == r) return val = (!x);
if (S[l] == S[r])
return val = (l + 1 == r) ? (!x) : Calc(x, l + 1, r - 1);
return val = (x > 0) ? (Calc(x - 1, l + 1, r) + Calc(x - 1, l, r - 1)) % Mod : 0;
}
int main () {
File();
Set(f, -1);
scanf ("%s", S + 1);
int m = strlen(S + 1), n = read() + m;
int l = (n + 1) / 2, n24 = m - 1, n25 = (m + 1) / 2, n26 = n25;
len = n24 + n25 + n26;
Mat base;
For (i, 1, n24)
base.a[i][i] = 24, base.a[i][i + 1] = 1;
For (i, n24 + 1, n24 + n25)
base.a[i][i] = 25, base.a[i][i + 1] = (i < iend), base.a[i][i + n25] = 1;
For (i, n24 + n25 + 1, len)
base.a[i][i] = 26;
Mat powa = fpm(base, l - 1), powb = powa * base;
int ans = 0;
For (i, 0, n24) {
int j = (m - i + 1) / 2, k = l - (i + j);
if (k >= 0) {
int coef = Calc(i, 1, m);
(ans += coef * powb.a[n24 - i + 1][n24 + n25 + j]) %= Mod;
if ((n & 1) && !((m - i) & 1))
(ans -= coef * powa.a[n24 - i + 1][n24 + j]) %= Mod;
}
}
printf ("%d
", (ans + Mod) % Mod);
return 0;
}
LYZ-Ice Skates
( exttt{source: POI2009})
题意
滑冰俱乐部初始有 (1 dots n) 号码溜冰鞋各 (k) 双，已知 (x) 号脚的人可以穿 (x dots x + d) 号码的鞋子。
现在有 (m) 次操作，每次两个数 (r,x) ，表示 (r) 号脚的人来了 (x) 个，(x) 为负表示离开。对于每次操作，输出溜冰鞋是否足够。
数据范围
(n, k, m le 5 imes 10^5, k le 10^9)
题解
显然这是一个二分图匹配的模型，直接跑显然是不行的。
考虑使用 (mathcal {Hall}) 定理进行判断，就是存在完美匹配的充要条件就是对于左边任意一个集合 (S) 来说，右边的和 (S) 内点的连边都要不小于 (|S|) 。
然后我们显然是考虑连边最小的那个集合，不难发现编号尽量连续的时候边会尽量少，也就是我们要对于所有区间 ([l, r]) 都要满足（记 (a_i) 为脚码为 (i) 的人的数量）：
我们移相化为：
然后用线段树维护最大子段和就可以判断了。复杂度是 (mathcal O(n log n)) 的。