striving & singing
今天上午写了总结，晚上打了队爷$\texttt{wyh}$的校内模拟赛。
$\texttt{OJ}$上没有上传，所以没链接。题目大意是给出一个排列，每次询问求区间$\texttt{mex}$。
因为是排列所以在当前区间没有出现的数一定在当前区间的补集里出现过，所以直接维护前缀和后缀最小值，然后每次直接$O(1)$查询补集最小值即可。
#include<cstdio>
int n, q, a[200100], premin[200100], sufmin[200100];
inline int min(int a, int b) { return a < b ? a : b; }
int main() {
freopen("seg.in", "r", stdin);
freopen("seg.out", "w", stdout);
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
premin[1] = a[1];
for (int i = 2; i <= n; i++) premin[i] = min(premin[i - 1], a[i]);
sufmin[n] = a[n];
for (int i = n - 1; i >= 1; i--) sufmin[i] = min(sufmin[i + 1], a[i]);
for (int i = 1; i <= q; i++) {
int l, r;
scanf("%d%d", &l, &r);
int ans = n;
if (l ^ 1) ans = min(ans, premin[l - 1]);
if (r ^ n) ans = min(ans, sufmin[r + 1]);
printf("%d\n", ans);
}
return 0;
}先用最短路求出来所有点被植入病毒的最晚时间$maxdis$。一个删点的状态能推迟时间仅当对于任意一个点所有和它距离小于等于$maxdis$的特殊点都被删除。可以把删点的集合按位压缩为一个整数，如果把每个点的和它距离小于等于$maxdis$的特殊点的集合记为$b_i$，则所有包含$b_i$的状态都能够推迟时间，因此可以$k$维前缀和。
比赛时我对于一个删点的状态的分析不到位，还以为只要距离最长的点的所有源点都被删了时间就推迟了，但实际上不是的，最后打了个纯暴力。高维前缀和的技巧是第一次见到，看起来还是挺有用的。
#include<cstdio>
#include<cstring>
#include<queue>
int n, m, k, sv[25], b[100100], ans;
long long dis[100100][25], maxdis;
bool vis[100100], flag[(1 << 20) + 10];
struct edge { int to, next, w; };
struct graph {
int ecnt, head[100100];
edge edges[400100];
inline void addedge(int u, int v, int w) {
edges[++ecnt].to = v;
edges[ecnt].w = w;
edges[ecnt].next = head[u];
head[u] = ecnt;
}
}g;
struct node {
int x; long long dis;
node(int xv = 0, long long dv = 0): x(xv), dis(dv) {}
bool operator < (const node &a) const { return dis > a.dis; }
};
std::priority_queue<node> q;
inline long long min(long long a, long long b) { return a < b ? a : b; }
inline long long max(long long a, long long b) { return a > b ? a : b; }
inline void dijkstra(int s) {
memset(vis, 0, sizeof(bool) * (n + 1));
dis[sv[s]][s] = 0;
q.push(node(sv[s], 0));
while (!q.empty()) {
node f = q.top();
q.pop();
if (vis[f.x]) continue;
vis[f.x] = true;
for (int i = g.head[f.x]; i; i = g.edges[i].next) {
int &v = g.edges[i].to, w = g.edges[i].w;
if (dis[v][s] > dis[f.x][s] + w) {
dis[v][s] = dis[f.x][s] + w;
q.push(node(v, dis[v][s]));
}
}
}
}
int main() {
freopen("network.in", "r", stdin);
freopen("network.out", "w", stdout);
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= k; i++) scanf("%d", &sv[i]);
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
g.addedge(u, v, w); g.addedge(v, u, w);
}
memset(dis, 0x3f, sizeof dis);
for (int i = 1; i <= k; i++) dijkstra(i);
for (int x = 1; x <= n; x++) {
long long d = 0x3fffffffffffffff;
for (int i = 1; i <= k; i++) d = min(d, dis[x][i]);
maxdis = max(maxdis, d);
}
for (int x = 1; x <= n; x++) {
for (int i = 1; i <= k; i++)
if (dis[x][i] <= maxdis) b[x] |= (1 << (i - 1));
flag[b[x]] = true;
}
for (int stt = 0; stt <= (1 << k) - 1; stt++) {
for (int i = 1; i <= k; i++)
if (stt & (1 << (i - 1))) flag[stt] = flag[stt] || flag[stt ^ (1 << (i - 1))];
if (!flag[stt]) ans++;
}
printf("%d\n", ans);
return 0;
}显然这是个区间$\texttt{DP}$。那么设$dp[i][j][k]$表示区间$[i,j]$最后$k$保留的概率，则有
$$dp[i][j][k]=\dfrac{1}{j-i}\sum_w\dfrac{a_k}{a_k+a_w}\sum_pdp[i][p][k]dp[p+1][j][w]$$
可以理解为枚举最后一次和$k$打的位置$w$，$k$和$w$在此之前合并的区间分别是区间前后缀，那么再枚举分割点，$O(n^5)$$\texttt{DP}$。$\dfrac{1}{j-i}$表示$k$和$w$最后一次打的概率。
实际上最后一维没用，可以设$f[i][j]$表示区间$[i,j]$最后$i$保留，$g[i][j]$表示区间$[i,j]$最后$j$保留。那么有：
$$f[i][j]=\dfrac{1}{j-i}\sum_{w=i+1}^jf[w][j]\dfrac{a_i}{a_i+a_w}\sum_{k=i}^{w-1}f[i][k]g[k+1][w]$$
$$g[i][j]=\dfrac{1}{j-i}\sum_{w=i}^{j-1}g[i][w]\dfrac{a_j}{a_j+a_w}\sum_{k=w}^{j-1}f[w][k]g[k+1][j]$$
最后答案就是$f[1][k]g[k][n]$。这样就可以$O(n^4)$$\texttt{DP}$了。
最后那个枚举分割点$k$的式子形式非常类似，那么可以发扬预处理精神，预处理$h[i][j]$：
$$h[i][j]=\sum_{k=i}^{j-1}f[i][k][k+1][j]$$
在枚举区间长度时，让$h$在$f$和$g$之前先更新即可。
因为是模意义下的概率所以需要求逆元，但如果边$\texttt{DP}$边算逆元会使复杂度再乘上一个$\log$，然后超时。继续发扬预处理精神，预处理逆元即可。总复杂度$O(n^3)$。
比赛时我一眼看出这是道区间$\texttt{DP}$，状态也设计出来了(虽然想出来的是$O(n^5)$做法的状态但毕竟还是能拿到分的)，但方程推得不对，样例都过不去，于是去写$\texttt{B}$题了。
#include<cstdio>
const int MOD = 998244353;
int n, k, a[510], f[510][510], g[510][510], h[510][510], suminv[510][510];
void exgcd(int a, int b, int &x, int &y) {
if (!b) { x = 1; y = 0; return; }
exgcd(b, a % b, y, x);
y -= a / b * x;
}
inline int inv(int a) { int x, y; exgcd(a, MOD, x, y); return (x % MOD + MOD) % MOD; }
int main() {
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++) suminv[i][j] = suminv[j][i] = inv(a[i] + a[j]);
for (int i = 1; i <= n; i++) f[i][i] = g[i][i] = 1;
for (int l = 2; l <= n; l++) {
for (int i = 1; i + l - 1 <= n; i++) {
int j = i + l - 1;
for (int k = i; k <= j - 1; k++) h[i][j] = (h[i][j] + (long long)f[i][k] * g[k + 1][j] % MOD) % MOD;
}
int invl = inv(l - 1);
for (int i = 1; i + l - 1 <= n; i++) {
int j = i + l - 1;
for (int w = i + 1; w <= j; w++)
f[i][j] = (f[i][j] + (long long)f[w][j] * a[i] % MOD * suminv[i][w] % MOD * h[i][w] % MOD) % MOD;
f[i][j] = (long long)f[i][j] * invl % MOD;
for (int w = i; w <= j - 1; w++)
g[i][j] = (g[i][j] + (long long)g[i][w] * a[j] % MOD * suminv[j][w] % MOD * h[w][j] % MOD) % MOD;
g[i][j] = (long long)g[i][j] * invl % MOD;
}
}
printf("%d\n", (int)((long long)g[1][k] * f[k][n] % MOD));
return 0;
}这场比赛我的分数是$100+24+0=124$，总排名第一，毕竟拿不到第一的话我就可以直接退役了。而且题目难度其实对我来说不算太难，但让我自己写又不容易写出来。
https://www.luogu.com.cn/problem/P1463
范围内的反素数实际上是约数个数最多的最小数。$\texttt{int}$范围内的数字最多只能有$10$个不同的质因子，质因子的指数最大是$30$。一个反质数的质因数指数一定单调不递增，否则可以交换两个逆序质因数，这样约数个数不变，且数字变小。根据这几条性质直接搜索即可。
#include<cstdio>
const int prime[11] = { 0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 };
int n, ans, anscnt;
inline int min(int a, int b) { return a < b ? a : b; }
void dfs(int x, int lst, int mul, int cnt) {
if (anscnt < cnt) anscnt = cnt, ans = mul;
else if (anscnt == cnt) ans = min(ans, mul);
if (x == 11) return;
int p = 1;
for (int i = 0; i <= lst; i++) {
if ((long long)mul * p > n) continue;
dfs(x + 1, i, mul * p, cnt * (i + 1));
p *= prime[x];
}
}
int main() {
scanf("%d", &n);
dfs(1, 30, 1, 1);
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P1593
把一个数质因数分解为$\prod_{i=1}^kp_i^{c_i}$，则这个数的所有因子的和为$\prod_{i=1}^k\sum_{j=0}^{c_i}p_i^j$。后面的和式实际上就是等比数列求和，即$\dfrac{p^{c_i+1}-1}{p_i-1}$。当$p_i\equiv 1\pmod {9901}$时$p_i-1$不存在逆元，但显然这个等比数列的值为$c_i+1$，这样就不需要计算逆元了。还有当$p_i\equiv 0\pmod{9901}$时$p_i-1$如果直接算就成了负数，需要加$9901$再模。
#include<cstdio>
const int MOD = 9901;
int a, b, d[15], c[15], pcnt, ans = 1;
inline void factorize(int x) {
for (int i = 2; i * i <= x; i++) {
if (x % i) continue;
d[++pcnt] = i;
while (!(x % i)) x /= i, c[pcnt]++;
}
if (x > 1) d[++pcnt] = x, c[pcnt]++;
}
inline int pwr(int x, int k) {
int ans = 1;
while (k) {
if (k & 1) ans = (long long)ans * x % MOD;
x = (long long)x * x % MOD;
k >>= 1;
}
return ans;
}
inline int inv(int x) { return pwr(x, MOD - 2); }
int main() {
scanf("%d%d", &a, &b);
factorize(a);
for (int i = 1; i <= pcnt; i++) c[i] *= b;
for (int i = 1; i <= pcnt; i++) {
if ((d[i] - 1) % MOD) ans = (long long)ans * (pwr(d[i], c[i] + 1) - 1 + MOD) % MOD * inv(d[i] - 1) % MOD;
else ans = (long long)ans * (c[i] + 1) % MOD;
}
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P3601
$qiandao(x)=x-\varphi(x)$。因此计算$\varphi$即可。$l,r$的范围较大，不能直接筛，但$r-l$比较小，可以枚举区间内的每个数。考虑欧拉函数的计算过程$\varphi(x)=x\prod_{i=1}^k(1-\dfrac{1}{p_i})$，如果直接对于每个数$O(\sqrt n)$暴力计算显然不行，但可以枚举质因子，对于每个质数计算它在$[l,r]$中对所有它的倍数的贡献。因为任意一个正整数数$x$最多只包含一个大于$\sqrt x$的质因子，所以可以预处理出来小于等于$\sqrt r$的所有质数，然后剩下一个质因子直接计算即可。
#include<cstdio>
const int MOD = 666623333;
int prime[100100], pcnt, ans;
long long l, r, phi[1000100], num[1000100];
bool isprime[1000100];
int main() {
scanf("%lld%lld", &l, &r);
for (int i = 0; i <= r - l; i++) num[i] = phi[i] = l + i;
for (int i = 2; (long long)i * i <= r; i++) isprime[i] = true;
for (int i = 2; (long long)i * i <= r; i++) {
if (isprime[i]) prime[++pcnt] = i;
for (int j = 1; j <= pcnt && (long long)i * prime[j] * i * prime[j] <= r; j++) {
isprime[i * prime[j]] = false;
if (!(i % prime[j])) break;
}
}
for (int i = 1; i <= pcnt; i++) {
int p = prime[i];
for (long long x = (l / p + (l % p ? 1 : 0)) * p; x <= r; x += p) {
phi[x - l] = phi[x - l] / p * (p - 1);
while (!(num[x - l] % p)) num[x - l] /= p;
}
}
for (int i = 0; i <= r - l; i++)
if (num[i] > 1) phi[i] = phi[i] / num[i] * (num[i] - 1), num[i] = 1;
for (int i = 0; i <= r - l; i++) ans = ((long long)ans + l + i - phi[i]) % MOD;
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P1835
和上题一样的方法，但是注意不要爆$\texttt{int}$。
#include<cstdio>
#include<cstring>
int l, r, prime[100100], pcnt, ans;
bool isprime[1000100];
int main() {
scanf("%d%d", &l, &r);
for (int i = 2; (long long)i * i <= r; i++) isprime[i] = true;
for (int i = 2; (long long)i * i <= r; i++) {
if (isprime[i]) prime[++pcnt] = i;
for (int j = 1; j <= pcnt && (long long)i * prime[j] * i * prime[j] <= r; j++) {
isprime[i * prime[j]] = false;
if (!(i % prime[j])) break;
}
}
memset(isprime, 1, sizeof isprime);
for (int i = 1; i <= pcnt; i++) {
int p = prime[i];
for (long long x = ((long long)l / p + (l % p ? 1 : 0)) * p; x <= r; x += p)
if (x ^ p) isprime[x - l] = false;
}
for (int i = 0; i <= r - l; i++)
if (isprime[i]) ans++;
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P3853
显然直接二分即可。注意特判相邻距离等于二分值的倍数的情况。
#include<cstdio>
int l, n, k, pos[100100];
bool check(int mid) {
int cnt = 0;
for (int i = 2; i <= n; i++)
cnt += (pos[i] - pos[i - 1]) / mid + ((pos[i] - pos[i - 1]) % mid ? 0 : -1);
return cnt <= k;
}
int main() {
scanf("%d%d%d", &l, &n, &k);
for (int i = 1; i <= n; i++) scanf("%d", &pos[i]);
int lx = 1, rx = l + 1;
while (lx < rx) {
int mid = lx + (rx - lx >> 1);
if (check(mid)) rx = mid;
else lx = mid + 1;
}
printf("%d\n", lx);
return 0;
}https://www.luogu.com.cn/problem/P3807
$$\binom{n}{m}\equiv\binom{n/p}{m/p}\binom{n\bmod p}{m\bmod p}\pmod p$$
其中$p$是质数。
注意特判$n<m$的情况。
#include<cstdio>
int t, fac[100100];
void exgcd(int a, int b, int &x, int &y) {
if (!b) { x = 1; y = 0; return; }
exgcd(b, a % b, y, x);
y -= a / b * x;
}
inline int inv(int a, int p) { int x, y; exgcd(a, p, x, y); return (x % p + p) % p; }
int binom(int n, int m, int p) {
if (n < m) return 0;
if (n < p && m < p) return (long long)fac[n] * inv(fac[m], p) % p * inv(fac[n - m], p) % p;
return (long long)binom(n / p, m / p, p) * binom(n % p, m % p, p) % p;
}
int main() {
scanf("%d", &t);
while (t--) {
int n, m, p;
scanf("%d%d%d", &n, &m, &p);
fac[0] = 1;
for (int i = 1; i <= p; i++) fac[i] = (long long)fac[i - 1] * i % p;
printf("%d\n", binom(n + m, m, p));
}
return 0;
}https://www.luogu.com.cn/problem/P4345
用 $\text{Lucas}$ 定理拆开后，发现$\left\lfloor\dfrac{i}{p}\right\rfloor$只有$\left\lfloor\dfrac{k}{p}\right\rfloor$种取值，于是可以用和整除分块类似的思想，枚举这个值，然后推式子，发现是一个递归式。
$$f(n,k)=\sum_{i=0}^k\dbinom{n}{i}\bmod 2333\\=\sum_{i=0}^k\dbinom{n/p}{i/p}\dbinom{n\bmod p}{i\bmod p}\\=\sum_{i=0}^{k/p-1}\dbinom{n/p}{i}\sum_{j=0}^{p-1}\dbinom{n\bmod p}{j}+\dbinom{n/p}{k/p}\sum_{j=0}^{k\bmod p}\dbinom{n\bmod p}{j}\\=f(n/p,k/p-1)f(n\bmod p,p-1)+\dbinom{n/p}{k/p}f(n\bmod p,k\bmod p)$$
于是可以$O(2333^2)$预处理$f$和组合数，然后和 $\text{Lucas}$ 定理一样递归求解。
#include<cstdio>
const int MOD = 2333;
int t, cn[2500][2500], fv[2500][2500];
int binom(long long n, long long m) {
if (n < m) return 0;
if (n < MOD && m < MOD) return cn[n][m];
return binom(n / MOD, m / MOD) * binom(n % MOD, m % MOD) % MOD;
}
int f(long long n, long long k) {
if (k < 0) return 0;
if (n < MOD && k < MOD) return fv[n][k];
return (f(n / MOD, k / MOD - 1) * f(n % MOD, MOD - 1) % MOD + binom(n / MOD, k / MOD) * f(n % MOD, k % MOD) % MOD) % MOD;
}
int main() {
scanf("%d", &t);
for (int i = 0; i < 2333; i++) cn[i][0] = fv[i][0] = 1;
for (int i = 0; i < 2333; i++) fv[0][i] = 1;
for (int i = 1; i < 2333; i++)
for (int j = 1; j < 2333; j++) {
cn[i][j] = (cn[i - 1][j] + cn[i - 1][j - 1]) % MOD;
fv[i][j] = (fv[i][j - 1] + cn[i][j]) % MOD;
}
while (t--) {
long long n, k;
scanf("%lld%lld", &n, &k);
printf("%d\n", f(n, k));
}
return 0;
}https://www.luogu.com.cn/record/list?user=116063
题目要求是实际上就是这个式子：
$$g^{\sum_{d|n}\binom{n}{n/d}}\bmod 999911659$$
可以用欧拉定理的推论处理指数：
$$g^{\sum_{d|n}\binom{n}{n/d}\bmod 999911658}\bmod 999911659$$
那么现在要求的就是这个式子：
$$\sum_{d|n}\binom{n}{n/d}\bmod 999911658\\=\sum_{d|n}\binom{n}{d}\bmod 999911658$$
把$999911658$质因数分解，得到$2,3,4679,35617$这四个质数。于是可以分别求解模这四个质数的方程，再用 $\text{CRT}$ 合并得到答案。
$$\begin{cases}x\equiv\sum_{d|n}\binom{n}{d}\pmod 2\\x\equiv\sum_{d|n}\binom{n}{d}\pmod 3\\x\equiv\sum_{d|n}\binom{n}{d}\pmod{4679}\\x\equiv\sum_{d|n}\binom{n}{d}\pmod{35617}\end{cases}$$
直接枚举所有约数，对于每个约数计算组合数。因为$n$的范围比较大，但模数很小，所以可以用 $\text{Lucas}$ 定理求组合数。
注意特判快速幂底数为$0$的情况。
#include<cstdio>
const int c[5] = { 0, 2, 3, 4679, 35617 }, MOD = 999911659, M = 999911658;
int n, g, fac[40000], invfac[40000], a[5];
inline int pwr(int x, int k, int p) {
if (!(x % p)) return 0;
int ans = 1;
while (k) {
if (k & 1) ans = (long long)ans * x % p;
x = (long long)x * x % p;
k >>= 1;
}
return ans % p;
}
inline int inv(int x, int p) { return pwr(x, p - 2, p); }
int binom(int n, int m, int p) {
if (n < m) return 0;
if (n < p && m < p) return (long long)fac[n] * invfac[m] % p * invfac[n - m] % p;
return (long long)binom(n / p, m / p, p) * binom(n % p, m % p, p) % p;
}
int getsum(int p) {
int ans = 0;
for (int i = 1; i * i <= n; i++) {
if (n % i) continue;
if (i ^ (n / i)) ans = ((ans + binom(n, i, p)) % p + binom(n, n / i, p)) % p;
else ans = (ans + binom(n, i, p)) % p;
}
return ans;
}
int crt() {
int ans = 0;
for (int i = 1; i <= 4; i++) ans = (ans + (long long)a[i] * (M / c[i]) % M * inv(M / c[i], c[i]) % M) % M;
return (ans % M + M) % M;
}
int main() {
scanf("%d%d", &n, &g);
for (int x = 1; x <= 4; x++) {
int p = c[x];
fac[0] = 1;
for (int i = 1; i < p; i++) fac[i] = (long long)fac[i - 1] * i % p;
invfac[p - 1] = inv(fac[p - 1], p);
for (int i = p - 2; i >= 0; i--) invfac[i] = (long long)invfac[i + 1] * (i + 1) % p;
a[x] = getsum(p);
}
printf("%d\n", pwr(g, crt(), MOD));
return 0;
}https://www.luogu.com.cn/problem/P2044
$$\begin{bmatrix}X_n\\1\end{bmatrix}=\begin{bmatrix}a&c\\0&1\end{bmatrix}\begin{bmatrix}X_{n-1}\\1\end{bmatrix}$$
当递推式要加上一个常数项时，可以在矩阵中加一个$1$，然后在转移矩阵中的对应位置填上常数项。
#include<cstdio>
#include<cstring>
int g;
long long m, a, c, x0, n;
inline long long mul(long long, long long);
struct matrix {
int l, w; long long a[3][3];
matrix(int lv = 0, int wv = 0): l(lv), w(wv) { memset(a, 0, sizeof a); }
long long* operator [] (const int &idx) { return &a[idx][0]; }
matrix operator * (matrix b) const {
matrix ans(l, b.w);
for (int i = 1; i <= ans.l; i++)
for (int j = 1; j <= ans.w; j++)
for (int k = 1; k <= w; k++)
ans[i][j] = (ans[i][j] + mul(a[i][k], b[k][j])) % m;
return ans;
}
inline void build() { for (int i = 1; i <= l; i++) a[i][i] = 1; }
}f(2, 1), trs(2, 2);
inline long long mul(long long x, long long k) {
long long ans = 0;
while (k) {
if (k & 1) ans = (ans + x) % m;
x = (x + x) % m;
k >>= 1;
}
return ans;
}
inline matrix pwr(matrix &x, long long k) {
matrix ans(x.l, x.w); ans.build();
while (k) {
if (k & 1) ans = ans * x;
x = x * x;
k >>= 1;
}
return ans;
}
int main() {
scanf("%lld%lld%lld%lld%lld%d", &m, &a, &c, &x0, &n, &g);
f[1][1] = x0; f[2][1] = 1;
trs[1][1] = a; trs[1][2] = c; trs[2][1] = 0; trs[2][2] = 1;
printf("%lld\n", (pwr(trs, n) * f)[1][1] % g);
return 0;
}https://www.luogu.com.cn/problem/P2886
设矩阵$A$为经过$i$条边的最短路，矩阵$B$为经过$j$条边的最短路，矩阵$C_{i,j}=\min\limits_{k=1}^n{A_{i,k}+B_{k,j}}$，则$C$就是经过$i+j$条边的最短路。
矩阵乘法满足结合律，因为
$$[(AB)C]{i,j}=\sum{l=1}^n\left(\sum_{k=1}^nA_{i,k}B_{k,l}\right)C_{l,j}\\=\sum_{k=1}^n\sum_{l=1}^nA_{i,k}B_{k,l}C_{l,j}\\=\sum_{k=1}^nA_{i,k}\left(\sum_{l=1}^nB_{k,l}C_{l,j}\right)\\=[A(BC)]_{i,j}$$
同样地，对于本题的矩阵运算，有
$$[(AB)C]{i,j}=\min\limits{l=1}^n{\min\limits_{k=1}^n{A_{i,k}+B_{k,l}}+C_{l,j}}\\=\min\limits_{k=1}^n\min\limits_{l=1}^n{A_{i,k}+B_{k,l}+C_{l,j}}\\=\min\limits_{k=1}^n{A_{i,k}+\min\limits_{l=1}^n{B_{k,l}+C_{l,j}}}\\=[A(BC)]_{i,j}$$
因此可以矩阵快速幂计算。
为了以后方便，再来自己编一下更为广义的矩阵运算结合律：
$$[(AB)C]{i,j}=\bigoplus{l=1}^n\left(\bigoplus_{k=1}^nA_{i,k}\otimes B_{k,l}\right)\otimes C_{l,j}\\=\bigoplus_{k=1}^n\bigoplus_{l=1}^nA_{i,k}\otimes B_{k,l}\otimes C_{l,j}\\=\bigoplus_{k=1}^nA_{i,k}\otimes \left(\bigoplus_{l=1}^nB_{k,l}\otimes C_{l,j}\right)\\=[A(BC)]_{i,j}$$
我用$\bigoplus$代替原来的$\sum$，因为这个符号看起来像一个加号加一个圈。同样地，用$\otimes$代替$\times$，因为这个符号像一个乘号加一个圈。根据这个式子，只要$(a\oplus b)\otimes c=(a\otimes c)\oplus(b\otimes c)$即满足分配律，对应的矩阵乘法就满足结合律。
所以说，因为$(a+b)\times c=a\times c+b\times c$，所以矩阵乘法满足结合律；因为$\min{a,b}+c=\min{a+c,b+c}$，所以本题的矩阵运算满足结合律。
#include<cstdio>
#include<cstring>
#include<algorithm>
int n, m, s, t, q, nodes[210], id[1010];
struct edge { int u, v, w; }edges[110];
inline int min(int, int);
struct matrix {
int l, w, a[210][210];
matrix(int lv = 0, int wv = 0): l(lv), w(wv) {}
int* operator [] (const int &idx) { return &a[idx][0]; }
matrix operator * (matrix b) {
matrix ans(l, b.w); ans.build();
for (int i = 1; i <= ans.l; i++)
for (int j = 1; j <= ans.w; j++)
for (int k = 1; k <= w; k++) ans[i][j] = min(ans[i][j], a[i][k] + b[k][j]);
return ans;
}
inline void build() { memset(a, 0x3f, sizeof a); }
inline void resize(int lv, int wv) { l = lv; w = wv; }
}g;
inline int min(int a, int b) { return a < b ? a : b; }
inline matrix pwr(matrix x, int k) {
matrix ans = x;
for (k--; k; x = x * x, k >>= 1)
if (k & 1) ans = ans * x;
return ans;
}
int main() {
scanf("%d%d%d%d", &q, &m, &s, &t);
for (int i = 1; i <= m; i++) scanf("%d%d%d", &edges[i].w, &edges[i].u, &edges[i].v), nodes[i * 2 - 1] = edges[i].u, nodes[i * 2] = edges[i].v;
std::sort(nodes + 1, nodes + m * 2 + 1);
n = std::unique(nodes + 1, nodes + m * 2 + 1) - nodes - 1;
for (int i = 1; i <= n; i++) id[nodes[i]] = i;
g.build(); g.resize(n, n);
for (int i = 1; i <= m; i++) {
int u = id[edges[i].u], v = id[edges[i].v];
g[u][v] = g[v][u] = min(edges[i].w, g[u][v]);
}
printf("%d\n", pwr(g, q)[id[s]][id[t]]);
return 0;
}https://www.luogu.com.cn/problem/P2233
设$f(x,i)$表示第$x$个点经过$i$条边的方案数，则有：
$$\begin{bmatrix}f(1,i)\\f(2,i)\\f(3,i)\\f(4,i)\\f(5,i)\\f(6,i)\\f(7,i)\\f(8,i)\end{bmatrix}=\begin{bmatrix}0&1&0&0&0&0&0&1\\1&0&1&0&0&0&0&0\\0&1&0&1&0&0&0&0\\0&0&1&0&0&0&0&0\\0&0&0&1&0&1&0&0\\0&0&0&0&0&0&1&0\\0&0&0&0&0&1&0&1\\1&0&0&0&0&0&1&0\end{bmatrix}\begin{bmatrix}f(1,i-1)\\f(2,i-1)\\f(3,i-1)\\f(4,i-1)\\f(5,i-1)\\f(6,i-1)\\f(7,i-1)\\f(8,i-1)\end{bmatrix}$$
注意第$5$个点没有出边，所以第$5$列的数字全为$0$，这样其他的点就无法从点$5$转移过来。
#include<cstdio>
#include<cstring>
const int MOD = 1000;
int n;
struct matrix {
int l, w, a[9][9];
matrix(int lv = 0, int wv = 0): l(lv), w(wv) { memset(a, 0, sizeof a); }
int* operator [] (const int &idx) { return &a[idx][0]; }
matrix operator * (matrix b) {
matrix ans(l, b.w);
for (int i = 1; i <= ans.l; i++)
for (int j = 1; j <= ans.w; j++)
for (int k = 1; k <= w; k++) ans[i][j] = (ans[i][j] + a[i][k] * b[k][j] % MOD) % MOD;
return ans;
}
inline void build() { for (int i = 1; i <= l; i++) a[i][i] = 1; }
}f(8, 1), trs(8, 8);
inline matrix pwr(matrix x, int k) {
matrix ans(x.l, x.w); ans.build();
for (; k; x = x * x, k >>= 1) if (k & 1) ans = ans * x;
return ans;
}
int main() {
f[1][1] = 1;
for (int i = 1; i <= 8; i++) trs[i][(i + 6) % 8 + 1] = trs[i][i % 8 + 1] = 1;
trs[4][5] = trs[6][5] = 0;
scanf("%d", &n);
printf("%d\n", (pwr(trs, n) * f)[5][1]);
return 0;
}https://www.luogu.com.cn/problem/P5789
和上一题的做法本质相同，设$f(x,i)$表示点$x$经过$i$条边的方案数，则若存在一条从$u$到$v$的单向边$(u,v)$，则对应转移矩阵$trs_{v,u}=1$。
对于停在原地，可以对每个点向自己连一条单向边；对于自爆，可以新建一个点，从每个点向这个点连一条单向边。
#include<cstdio>
#include<cstring>
const int MOD = 2017;
int n, m, t, ans;
struct matrix {
int l, w, a[110][110];
matrix(int lv = 0, int wv = 0): l(lv), w(wv) { memset(a, 0, sizeof a); }
int* operator [] (const int &idx) { return &a[idx][0]; }
matrix operator * (matrix b) {
matrix ans(l, b.w);
for (int i = 1; i <= ans.l; i++)
for (int j = 1; j <= ans.w; j++)
for (int k = 1; k <= w; k++) ans[i][j] = (ans[i][j] + a[i][k] * b[k][j]) % MOD;
return ans;
}
inline void resize(int lv, int wv) { l = lv; w = wv; }
inline void build() { for (int i = 1; i <= l; i++) a[i][i] = 1; }
}g, f;
inline matrix pwr(matrix x, int k) {
matrix ans(x.l, x.w); ans.build();
for (; k; x = x * x, k >>= 1) if (k & 1) ans = ans * x;
return ans;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v);
g[u][v] = g[v][u] = 1;
}
for (int i = 1; i <= n + 1; i++) g[i][i] = g[n + 1][i] = 1;
f[1][1] = 1;
g.resize(n + 1, n + 1); f.resize(n + 1, 1);
scanf("%d", &t);
f = pwr(g, t) * f;
for (int i = 1; i <= n + 1; i++) ans = (ans + f[i][1]) % MOD;
printf("%d\n", ans);
return 0;
}https://www.luogu.com.cn/problem/P3216
设$f(i)$表示$\text{Concatenate(i)}$，$bit(i)=\left\lfloor\lg i\right\rfloor$，则有：
$$f(i)=f(i-1)10^{bit(i)}+i$$
那么可以得出：
$$\begin{bmatrix}f(i)\\i\\1\end{bmatrix}=\begin{bmatrix}10^{bit(i)}&1&1\\0&1&1\\0&0&1\end{bmatrix}\begin{bmatrix}f(i-1)\\i-1\\1\end{bmatrix}$$
$bit(i)$并不容易在递推的同时处理，因此可以枚举$bit(i)$的值，然后分段计算，复杂度$O(\lg n\log_2n)$，可以通过。
#include<cstdio>
#include<cstring>
int m;
long long n;
struct matrix {
int l, w, a[4][4];
matrix(int lv = 0, int wv = 0): l(lv), w(wv) { memset(a, 0, sizeof a); }
inline int* operator [] (const int &idx) { return &a[idx][0]; }
inline matrix operator * (matrix b) {
matrix ans(l, b.w);
for (int i = 1; i <= ans.l; i++)
for (int j = 1; j <= ans.w; j++)
for (int k = 1; k <= w; k++) ans[i][j] = (ans[i][j] + (long long)a[i][k] * b[k][j] % m) % m;
return ans;
}
inline void build() { for (int i = 1; i <= l; i++) a[i][i] = 1; }
}f(3, 1), trs(3, 3);
inline matrix pwr(matrix x, long long k) {
matrix ans(x.l, x.w); ans.build();
for (; k; x = x * x, k >>= 1) if (k & 1) ans = ans * x;
return ans;
}
inline long long min(long long a, long long b) { return a < b ? a : b; }
int main() {
scanf("%lld%d", &n, &m);
f[1][1] = f[2][1] = 0; f[3][1] = 1;
trs[1][2] = trs[1][3] = trs[2][2] = trs[2][3] = trs[3][3] = 1;
for (long long bit = 10; bit / 10 <= n; bit *= 10) {
trs[1][1] = bit % m;
f = pwr(trs, min(bit - 1, n) - bit / 10 + 1) * f;
if (bit == 1e18) break;
}
printf("%d\n", f[1][1]);
return 0;
}https://www.luogu.com.cn/problem/P2129
每次操作都可以看作一次矩阵乘法：
$$\begin{bmatrix}1&0&p\\0&1&q\\0&0&1\end{bmatrix}\begin{bmatrix}x\\y\\1\end{bmatrix}=\begin{bmatrix}x+p\\y+q\\1\end{bmatrix}$$
$$\begin{bmatrix}-1&0&0\\0&1&0\\0&0&1\end{bmatrix}\begin{bmatrix}x\\y\\1\end{bmatrix}=\begin{bmatrix}-x\\y\\1\end{bmatrix}$$
$$\begin{bmatrix}1&0&0\\0&-1&0\\0&0&1\end{bmatrix}\begin{bmatrix}x\\-y\\1\end{bmatrix}$$
因此直接把操作矩阵乘起来即可。
#include<cstdio>
#include<cstring>
int n, m;
struct matrix {
int l, w; long long a[4][4];
matrix(int lv = 0, int wv = 0): l(lv), w(wv) { memset(a, 0, sizeof a); }
inline long long* operator [] (const int &idx) { return &a[idx][0]; }
inline matrix operator * (matrix b) {
matrix ans(l, b.w);
for (int i = 1; i <= ans.l; i++)
for (int j = 1; j <= ans.w; j++)
for (int k = 1; k <= w; k++) ans[i][j] += a[i][k] * b[k][j];
return ans;
}
}trs(3, 3), opt1(3, 3), opt2(3, 3), opt3(3, 3), points[500100];
struct operation {
int opt; long long p, q;
}opts[500100];
inline char read() {
register char c = getchar();
while (c == ' ' || c == '\n' || c == '\r') c = getchar();
return c;
}
int main() {
for (int i = 1; i <= 3; i++) trs[i][i] = opt1[i][i] = opt2[i][i] = opt3[i][i] = 1;
opt2[1][1] = -1; opt3[2][2] = -1;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%lld%lld", &points[i][1][1], &points[i][2][1]), points[i][3][1] = 1, points[i].l = 3, points[i].w = 1;
for (int i = 1; i <= m; i++) {
char opt = read();
if (opt == 'm') opts[i].opt = 1, scanf("%lld%lld", &opts[i].p, &opts[i].q);
else if (opt == 'x') opts[i].opt = 2;
else if (opt == 'y') opts[i].opt = 3;
}
for (int i = m; i >= 1; i--) {
if (opts[i].opt == 1) opt1[1][3] = opts[i].p, opt1[2][3] = opts[i].q, trs = opt1 * trs;
else if (opts[i].opt == 2) trs = opt2 * trs;
else if (opts[i].opt == 3) trs = opt3 * trs;
}
for (int i = 1; i <= n; i++) points[i] = trs * points[i], printf("%lld %lld\n", points[i][1][1], points[i][2][1]);
return 0;
}https://www.luogu.com.cn/problem/P3166
首先把$n,m$加$1$，使得格子数转化为点数。
如果不考虑三点共线，那么答案就是$\dbinom{nm}{3}$。根据之前容斥原理的补集转化公式，可以用总方案数减去三点共线的方案数，得到三点不共线的方案数。三点共线，可以分为横着共线，竖着共线，和斜着共线。显然，横着共线的方案数为$m\dbinom{n}{3}$，竖着共线的方案数为$n\dbinom{m}{3}$。对于斜着共线，可以枚举两个点，若它们之间的线段上有$k$个点可以选(端点不算)，则方案数就是$k$。
有一个结论：若两个点之间的坐标差分别为$x,y$，则算上这两个点，以这两个点为端点的线段上一共有$(\gcd(i,j)+1)$个整点。考虑对于$x,y$，若存在一个公因数$d$大于$1$，则可以把线段平均分为$d$份，使得分出来的每个线段的端点都是整点。因此最多可以分出$\gcd(x,y)$个端点都是整点的线段，他们的端点数为$\gcd(x,y)+1$。
因此，可以枚举两个点的坐标差$x,y$，然后方案数就是$2(n-x)(m-y)(\gcd(x,y)-1)$。
#include<cstdio>
int n, m;
long long ans;
int gcd(int a, int b) {
if (!b) return a;
return gcd(b, a % b);
}
int main() {
scanf("%d%d", &n, &m); n++, m++;
ans = (long long)(n * m) * (n * m - 1) * (n * m - 2) / 6;
if (m >= 3) ans -= (long long)n * m * (m - 1) * (m - 2) / 6;
if (n >= 3) ans -= (long long)m * n * (n - 1) * (n - 2) / 6;
for (int i = 1; i <= n - 1; i++)
for (int j = 1; j <= m - 1; j++) ans -= (long long)(n - i) * (m - j) * (gcd(i, j) - 1) * 2;
printf("%lld\n", ans);
return 0;
}$8$月$30$号去一中报到，$9$月$1$号开始军训，然后这几天就没怎么做题，把仅做的一题写在这里了。
https://www.luogu.com.cn/problem/P1351
可以枚举中转点$x$，然后父节点和所有子节点之间的贡献就是$w_{fa}\sum_{s\in S}w_s$。然后还得算所有子节点两两的贡献，可以考虑每个子节点的权值乘上所有子节点的权值，即$(\sum w_s)^2$，但这样会多算自己乘自己的贡献，所以还要减去$\sum w_s^2$。
#include<cstdio>
const int MOD = 10007;
int n, w[200100], ans1, ans2;
struct edge { int to, next; };
struct graph {
int ecnt, head[200100];
edge edges[400100];
inline void addedge(int u, int v) {
edges[++ecnt].to = v;
edges[ecnt].next = head[u];
head[u] = ecnt;
}
}g;
inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }
void dfs(int x, int fa) {
int maxw = 0, maxsecw = 0, sumw = 0, sumw2 = 0;
for (int i = g.head[x]; i; i = g.edges[i].next) {
int &v = g.edges[i].to;
if (v == fa) continue;
ans1 = max(ans1, w[fa] * w[v]);
ans2 = (ans2 + w[fa] * w[v] * 2) % MOD;
maxsecw = min(maxw, max(maxsecw, w[v]));
maxw = max(maxw, w[v]);
sumw = (sumw + w[v]) % MOD;
sumw2 = (sumw2 + w[v] * w[v]) % MOD;
dfs(v, x);
}
ans1 = max(ans1, maxw * maxsecw);
ans2 = (ans2 + sumw * sumw - sumw2) % MOD;
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int u, v; scanf("%d%d", &u, &v);
g.addedge(u, v); g.addedge(v, u);
}
for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
dfs(1, 0);
printf("%d %d\n", ans1, ans2);
return 0;
}