[HEOI2014]林中路径

题目链接

对于一组 latex S-T,设 latex d_i 为长为 latex i-1 的路径。则 latex ans_k=\sum\limits_{i=1}^{k}d_i(i-1)^2

\begin{split} ans_{2k}&=\sum_{i=1}^{2k}{d_i(i-1)^2}\\ &=\sum_{i=1}^k{d_i(i-1)^2}+\sum_{i=1}^k{d_{i+k}(i+k-1)^2}\\ &=\sum_{i=1}^k{d_i(i-1)^2}+\sum_{i=1}^k{d_{i+k}(i-1)^2}+k^2\sum_{i=1}^k{d_{i+k}}+2k\sum_{i=1}^k {d_{i+k}}\\ \end{split}

latex f_k=\sum\limits_{i=1}^{k}d_i(i-1)
\begin{split} f_{2k}&=\sum_{i=1}^{2k}{d_i(i-1)}\\ &=\sum_{i=1}^k{d_i(i-1)}+\sum_{i=1}^k{d_{i+k}(i+k-1)}\\ &=\sum_{i=1}^k{d_i(i-1)}+\sum_{i=1}^k{d_{i+k}(i-1)}+k\sum_{i=1}^k{d_{i+k}} \end{split}

latex g_k=\sum\limits_{i=1}^{k}a_i
\begin{split} g_{2k}&=\sum_{i=1}^{2k}{d_i}\\ &=\sum_{i=1}^k{d_i}+\sum_{i=1}^k{d_{i+k}}\\ \end{split}

latex D 为邻接矩阵,latex I 为单位矩阵,latex Glatex g 构成的矩阵,latex Flatex f 构成的矩阵,latex Alatex ans 构成的矩阵。
\begin{split} &G_1=I\\ &G_{2k}=G_k+G_k*D^k\\ &G_{k+1}=G_k+D^{k}\\ &F_1=0\\ &F_{2k}=F_k+F_kD^k+kG_kD^k\\ &F_{k+1}=F_k+kD^k\\ &A_1=0\\ &A_{2k}=A_k+A_kD^k+2kF_kD^k+k^2G_kD^k\\ &A_{k+1}=A_k+k^2D^k \end{split}

倍增地求出矩阵。复杂度 latex O(n^3logk+q)

#include <cstdio>
#include <cctype>
#include <cstring>
using namespace std;
int read() {
	int x = 0, f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}

const int Max = 103;
const int mod = 1000000007;
int n, m, K, Q, now;
void Add(int &a, int b) {
	a = (a + b) % mod;
}

struct Matrix {
	int a[Max][Max];
	Matrix() { memset(a, 0, sizeof a); }
	friend Matrix operator* (const Matrix &a, const int &b) {
		Matrix re;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				Add(re.a[i][j], 1ll * a.a[i][j] * b % mod);
		return re;
	}
	friend Matrix operator* (const Matrix &a, const Matrix &b) {
		Matrix re;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				for (int k = 1; k <= n; k++)
					Add(re.a[i][j], 1ll * a.a[i][k] * b.a[k][j] % mod);
		return re;
	}
	friend Matrix operator+ (const Matrix &a, const Matrix &b) {
		Matrix re;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				Add(re.a[i][j], (a.a[i][j] + b.a[i][j]) % mod);
		return re;
	}
} A[33], F[33], G[33], D, tD, tF, tG;

void solve(int K, int d) {
	if (K == 1) {
		for (int i = 1; i <= n; i++)
			G[d].a[i][i] = 1;
		tD = D, now = 1;
		return;
	}
	solve(K >> 1, d + 1);
	int k = K >> 1;
	tF = F[d + 1] * tD, tG = G[d + 1] * tD;
	F[d] = F[d + 1] + tF + tG * k;
	G[d] = G[d + 1] + tG;
	A[d] = A[d + 1] + A[d + 1] * tD + tF * (2ll * k % mod) + tG * (1ll * k * k % mod);
	tD = tD * tD, now <<= 1;
	if (K & 1) {
		G[d] = G[d] + tD;
		F[d] = F[d] + tD * (K - 1);
		A[d] = A[d] + tD * (1ll * (K - 1) * (K - 1) % mod);
		tD = tD * D, now |= 1;
	}
}

int main() {
	scanf("%d%d%d%d", &n, &m, &K, &Q);
	for (int i = 1; i <= m; i++) {
		int u = read(), v = read();
		D.a[u][v]++;
	}
	solve(K + 1, 0);
	while (Q--) {
		int s = read(), t = read();
		printf("%d\n", A[0].a[s][t]);
	}
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注