闲话
今日闲话【碎片】(0.8/1)
杂题
令积性函数 \(f\) 满足 \(f(p^c)=p^{\gcd(c,k)}\)，其中 \(k\) 为给定常数，\(p\) 为素数，\(c\) 为正整数。给定 \(n,m,k\)，请求出
\[\sum_{i=1}^n\sum_{j=1}^mf(ij)\pmod{10^9+7} \]\(1\le n\le 10^5, 1\le m\le 10^{10}, 1\le k \le 10^9\)。
看到 \(n\le 10^5\) 我们就想到了 DZY loves math IV。受它的启发，我们考虑枚举 \(n\)，对 \(F(i, m) = \sum_{j = 1}^m f(ij)\) 构造递归关系。
边界是 \(i = 1\)，这时 \(F(i, m)\) 退化成 \(f\) 的前缀和。这可以构造 PN 筛求解。具体地，我们考虑 \(g(n) = n\)，这前缀和可以 \(O(1)\) 地求出。随后我们可以 \(O(\sqrt m \log m)\) 地构造 PN 筛，单次求解是 \(O(\sqrt m)\) 的。
随后考虑 \(i > 1\) 的情况。设这时计算的是 \(F(n, m)\) 我们可以预料到，\(F\) 可能存在一种递归形式，这形式可以指数级地缩减 \(F\) 的两维信息。不妨向这方面接着思考，考虑 \(\text{Min_25}\) 筛的形式，找一个（最大）质因子做容斥。
考虑 \(p\mid n\)，设 \(c\) 是 \(n\) 中 \(p\) 的次数，并设 \(n' = n / p^c\)。知道这 \(p^c\) 一定会在这次计算中被剔除。考虑枚举 \(\le m\) 的值中 \(p\) 的次数恰好为 \(i\) 的部分，用至少 \(i\) 次的贡献减去至少 \(i + 1\) 次的贡献。至少 \(i\) 次的贡献显然就是 \(F(n', \left\lfloor \frac{m}{p^i}\right\rfloor)\)，而 \(i + 1\) 次的情况和这略有不同。我们钦定了这部分的值中至少有一个 \(p\)，但我们已经把它除掉了，因此需要在求和的 \(f(n'i)\) 内补上一个 \(p\)，也就是 \(F(n'p, \left\lfloor \frac{m}{p^{i + 1}}\right\rfloor)\)。乘上这部分的贡献 \(f(p^{i + c})\) 就得到了
可以记忆化暴力递归。题解说极限数据下，转移量和状态量分别是 \(26116544\)，\(1810443\)，所以暴力递归是对的。
但是可能会 T 掉一些点，因为常数太大。这时预处理一下 \(n\times m\le 10^6\) 的状态就可以通过了。题解说极限数据下，转移量和状态量下降到 \(13139202\)，\(972667\)。
复杂度？大概可以通过 \(\text{Min_25}\) 筛的复杂度证明得到一个比较优秀的界。当然 min25 筛也是打表得到的复杂度证明，所以不用管复杂度了吧。
code
#include <bits/stdc++.h>
using namespace std;
#define inline __attribute__((__gnu_inline__, __always_inline__, __artificial__)) inline
using pii = pair<int,int>; using vi = vector<int>; using vp = vector<pii>; using ll = long long;
using ull = unsigned long long; using db = double; using ld = long double; using lll = __int128_t;
template<typename T1, typename T2> T1 max(T1 a, T2 b) { return a > b ? a : b; }
template<typename T1, typename T2> T1 min(T1 a, T2 b) { return a < b ? a : b; }
#define multi int _T_; cin >> _T_; for (int TestNo = 1; TestNo <= _T_; ++ TestNo)
#define timer cerr << 1. * clock() / CLOCKS_PER_SEC << '\n';
#define iot ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
#define eb emplace_back
#define pb pop_back
const int N = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fll;
int n, k;
ll m;
int gpf[N], pfe[N], dv[N], prime[N], cnt, fv[N];
bool vis[N];
void sieve(int n) {
fv[1] = 1;
rep(i,2,n) {
if (!vis[i]) prime[++ cnt] = i, gpf[i] = i, pfe[i] = 1, dv[i] = 1;
rep(j,1,cnt) {
int t = i * prime[j]; if (t > n) break;
vis[t] = 1, gpf[t] = gpf[i];
dv[t] = dv[i] * (prime[j] == gpf[i] ? 1 : prime[j]);
pfe[t] = pfe[i] + (prime[j] == gpf[i]);
if (i % prime[j] == 0) break;
} fv[i] = fv[dv[i]] * qp(gpf[i], __gcd(k, pfe[i]));
}
}
int h[N][35];
void inith() {
rep(i,1,cnt) {
h[i][0] = 1;
for (ll j = 1, x = prime[i]; x <= m; ++ j, x = x * prime[i]) {
h[i][j] = (x <= 1e5 ? fv[x] : qp(prime[i], __gcd((int)j, k)));
for (ll k = 1, y = prime[i]; k <= j; ++ k, y = y * prime[i]) {
subi(h[i][j], mul(h[i][j - k], y));
}
}
}
}
vector<pair<ll, int>> pn;
void dfspn(ll va, int hv, int now) {
if (hv == 0) return;
pn.eb(va, hv);
rep(i,now,cnt) {
if (va > m / prime[i] / prime[i]) break;
for (ll j = 2, x = va * prime[i] * prime[i]; x <= m; ++ j, x = x * prime[i]) {
dfspn(x, mul(hv, h[i][j]), i + 1);
}
}
}
int calcg(ll n) { n = Mod(n); return mul(n + 1, n, inv(2)); }
vi _f[N];
struct _hsh {
template<typename T1>
size_t operator()(const T1& p) const {
return 1ll * p.first * 131 + p.second;
}
}; unordered_map<pair<int, ll>, int, _hsh> mp;
int f(int n, ll m) {
if (m == 0) return 0;
if (1ll * n * m <= 1e6) return _f[n][m];
if (mp.count({n,m})) return mp[{n,m}];
if (n == 1) {
int ret = 0;
for (auto [va, hv] : pn) {
if (va > m) break;
addi(ret, mul(hv, calcg(m / va)));
} return mp[{n,m}] = ret;
} else {
int ret = 0;
for (ll i = 0, x = m; x; ++ i, x /= gpf[n]) {
addi(ret, mul(sub(f(dv[n], x), f(dv[n] * gpf[n], x / gpf[n])), qp(gpf[n], __gcd(i + pfe[n], (ll)k))));
} return mp[{n,m}] = ret;
}
}
signed main() {
cin >> n >> m >> k;
sieve(1e6), cnt = lower_bound(prime + 1, prime + 1 + cnt, 1e5) - prime, inith(), dfspn(1, 1, 1);
sort(pn.begin(), pn.end());
_f[0] = vi(1e6 + 1, 0);
rep(i,1,1e6) {
_f[i].eb(0);
for (int j = 1; j * i <= 1e6; ++ j) {
_f[i].eb(add(_f[i][j - 1], fv[i * j]));
}
}
int ans = 0;
rep(i,1,n) addi(ans, f(i, m));
cout << ans << '\n';
}
给定一棵 \(n\) 个点的树（\(1\le n\le 10^5\)），树上有一条蛇，蛇覆盖了从蛇头 \(S\) 到蛇尾 \(T\) 的简单路径（\(S\neq T\)）。
蛇可以有两种移动方式：
- 蛇头向周围没有被覆盖的位置移动一个单位，蛇尾向蛇头的方向挪动一个单位；
- 蛇尾向周围没有被覆盖的位置移动一个单位，蛇头向蛇尾的方向挪动一个单位。
问蛇能否将头和尾的位置调换，即蛇头移动到 \(T\)、蛇尾移动到 \(S\)。
多次询问（不超过 \(100\) 组），每次给定树和 \(S,T\)。
3000？300！
首先考虑蛇能在哪些地方转身。这样的地方一定可以被一个关键点代表，其满足存在三条两两交为该点、且一个端点为该点的长度大于等于蛇长度的链。
必要性比较显然，但是没有充分性，因为蛇可能无法移动。
同时可以发现，如果能到达一个关键点则一定能到达其他所有关键点，因为可以在这里转向任意子树。
因此我们只需要找一个关键点，看蛇是否能到达这个关键点。
我们可以自然地构造一种方案：将这个关键点作为根，我们让蛇尽量向叶子移动。
蛇能到达这个点当且仅当存在一个移动方式，使得蛇的两头对应点的 LCA 是其中一个头对应的点。
总时间复杂度 \(O(Tn)\)。
给你一个串 \(S\) 以及一个字符串数组 \(T_{1\ldots m}\)，\(q\) 次询问，每次问 \(S\) 的子串 \(S[p_l\ldots p_r]\) 在 \(T_{l\ldots r}\) 中的哪个串里的出现次数最多，并输出出现次数。如有多解输出最靠前的那一个。
\(1\le |S|, q\le 5\times 10^5, 1\le m \le 5\times 10^4\)。
总感觉我写题解了 是我的错觉吗？
题解提示你了！是 suffixtree！
所以先建出后缀链接树。具体地，我们构造这 \(m\) 个串的 GSA，每个点记录所属的串的编号。提出 GSA 的后缀链接树，随后用动态开点线段树合并子树编号。
考虑任意子串都是前缀的后缀，因此考虑先预处理 \(S\) 的每个前缀在 GSA 上的匹配位置/匹配长度，设 \(S[1, k]\) 的位置是 \(pos(k)\)，长度为 \(len(k)\)。
然后考虑回答询问。如果 \(len(r) < pr - pl + 1\) 显然是无解的，反之考虑从 \(pos(r)\) 倍增到 \(l\) 所属的节点，也就是节点 \(p\) 使得 \(len[p]\ge pr - pl + 1\)，这时这个点一定包含（只有？） \(S[pl, pr]\)。
这样这个点对应线段树内 \([l, r]\) 区间最前面的最大值就是答案。
考虑 \(q, \sum |T|, |S| = O(n)\)，有总时间复杂度 \(O(n\log n)\)。
给定两个字符串 \(s_1, s_2\)，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。
\(1\le |s_1|, |s_2| \le 2\times 10^5\)。
每日水紫时刻。
考虑构造这两个串的 GSA，并记录每个字符对应的节点位置。
然后分开合并 endpos，就是用两个数组分别记录子树和。假设这两个数组是 \(siz1[], siz2[]\)。
把答案拆分开。记 GSA 的节点数是 \(m\)，以及 \(i\) 节点对应状态包含的串数为 \(len[i]\)。可以知道答案就是
\[\sum_{i = 1}^m siz1[i]\times siz2[i] \times len[i] \]可以在 \(O(n)\) 的复杂度内求解。
code
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<int,int>; using vi = vector<int>;
#define rep(i, s, t) for (register auto i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i, s, t) for (register auto i = (s), i##_ = (t) - 1; i > i##_; -- i)
#define iot ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define timer cerr << 1. * clock() / CLOCKS_PER_SEC << '\n'
#define eb emplace_back
const int N = 2e6 + 10;
int n1, n2; ll ans;
char s1[N], s2[N];
int len[N], link[N], son[N][26], siz[2][N], mlc = 1, lst = 1;
void extend(int c, int bel) {
int now = ++ mlc, p = lst;
len[now] = len[p] + 1;
siz[bel][now] = 1;
while (p and !son[p][c])
son[p][c] = now, p = link[p];
if (!p) link[now] = 1;
else {
int q = son[p][c];
if (len[q] == len[p] + 1) link[now] = q;
else {
int kage = ++ mlc;
len[kage] = len[p] + 1;
link[kage] = link[q];
link[q] = link[now] = kage;
memcpy(son[kage], son[q], sizeof son[kage]);
while (p and son[p][c] == q)
son[p][c] = kage, p = link[p];
}
} lst = now;
}
vi g[N];
void build() {
rep(i,2,mlc) g[link[i]].eb(i);
function<void(int)> dfs = [&](auto u) {
for (auto v : g[u]) dfs(v), siz[0][u] += siz[0][v], siz[1][u] += siz[1][v];
// cerr << siz[0][u] << ' ' << siz[1][u] << ' ' << len[u] - len[link[u]] << '\n';
ans += 1ll * siz[0][u] * siz[1][u] * (len[u] - len[link[u]]);
}; dfs(1);
}
signed main() {
iot; cin >> s1 + 1 >> s2 + 1;
n1 = strlen(s1 + 1), n2 = strlen(s2 + 1);
rep(i,1,n1) extend(s1[i] - 'a', 0);
lst = 1;
rep(i,1,n2) extend(s2[i] - 'a', 1);
build();
cout << ans << '\n';
}
今日多项式？目前是四道题！
标签：prime,10,le,20,int,闲话,23.3,__,using From： https://www.cnblogs.com/joke3579/p/chitchat230320.html