CF1970E3-Trails (Hard)

CF1970E3 Trails (Hard) 题解

题目

题目大意: 给定 mm 个点. 每个点都和一个共同的中心点有若干条路径. 对于第 ii 个点, 有 sis_i 条短路径, lil_i 条长路径. 一个小人开始在 11 号点, 每天他要走两条路径到达一个点(可以和出发点相同), 要求每天走过的路径至少有一条长路径. 问走 nn 天后, 所有合法路径的方案数.

1≤m≤105,1≤n≤1091 \leq m \leq 10^5, 1 \leq n \leq 10^9

思路

一个朴素的想法是递推.

设第 ii 天在 jj 号点的方案数为 ai,ja_{i,j}.

则有

ai,j=∑k=1m(sjsk+ljsk+sjlk)⋅ai−1,k\begin{aligned} a_{i, j} &= \sum_{k = 1}^{m}{(s_j s_k + l_j s_k + s_j l_k) \cdot a_{i - 1, k}} \end{aligned}

令 wi,j=sisj+lisj+siljw_{i, j} = s_i s_j + l_i s_j + s_i l_j 也就是

[ai,1ai,2⋮ai,m]=[w1,1w1,2⋯w1,mw2,1w2,2⋯w2,m⋮⋮⋱⋮wm,1wm,2⋯wm,m][ai−1,1ai−1,2⋮ai−1,m] \begin{bmatrix} {a_{i,1}}\\\\ {a_{i,2}}\\\\ \vdots\\\\ {a_{i, m}} \end{bmatrix} = \begin{bmatrix} {w_{1, 1}} & w_{1,2} & \cdots & w_{1, m} \\\\ {w_{2, 1}} & w_{2,2} & \cdots & w_{2, m} \\\\ \vdots & \vdots & \ddots & \vdots \\\\ {w_{m, 1}} & w_{m,2} & \cdots & w_{m, m} \\\\ \end{bmatrix} \begin{bmatrix} {a_{i - 1,1}}\\\\ {a_{i - 1,2}}\\\\ \vdots\\\\ {a_{i - 1, m}} \end{bmatrix}

使用矩阵快速幂可以解决.

但是我们发现 1≤m≤1051 \leq m \leq 10^5 我们甚至连一次矩阵乘法都做不完!

我们发现

wi,j=sisj+lisj+silj=(si+li)⋅(sj+lj)−li⋅lj\begin{align} w_{i, j} &= s_i s_j + l_i s_j + s_i l_j \nonumber \\\\ &= (s_i + l_i) \cdot (s_j + l_j) - l_i \cdot l_j \nonumber \end{align}

这何尝不是一种矩阵乘法?

于是我们构造矩阵

A=[s1+l1l1s2+l2l2⋮⋮sn+lnln]A = \begin{bmatrix} {s_1 + l_1} & l_1\\\\ {s_2 + l_2} & l_2\\\\ \vdots & \vdots\\\\ {s_n + l_n} & l_n\\\\ \end{bmatrix}

B=[s1+l1s2+l2⋯m2+lm−l1−l2⋯−lm]B = \begin{bmatrix} {s_1 + l_1} & {s_2 + l_2} & \cdots & {m_2 + l_m}\\\\ -l_1 & -l_2 & \cdots & -l_m\\\\ \end{bmatrix}

那么

[an,1an,2⋮an,m]=(AB)n[a0,1a0,2⋮a0,m]=A(BA)n−1B[a0,1a0,2⋮a0,m]\begin{aligned} \begin{bmatrix} {a_{n,1}}\\\\ {a_{n,2}}\\\\ \vdots\\\\ {a_{n, m}} \end{bmatrix} &=(A B)^n \begin{bmatrix} {a_{0, 1}}\\\\ {a_{0, 2}}\\\\ \vdots\\\\ {a_{0, m}} \end{bmatrix}\\\\ &= A (B A)^{n - 1} B \begin{bmatrix} {a_{0, 1}}\\\\ {a_{0, 2}}\\\\ \vdots\\\\ {a_{0, m}} \end{bmatrix} \end{aligned}

而 BABA 是一个二阶矩阵, 可以计算!

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<stack>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define frep(i,a,b) for(int i=a;i<(b);++i)
#define drep(i,a,b) for(int i=a;i>=(b);--i)
#define ls tree[p].l
#define rs tree[p].r
#define mid ((l + r) >> 1)
typedef long long ll;
typedef unsigned long long ull;
#define Maxq priority_queue<int,vector<int>,greater<int> >
using namespace std;
int mylog(int a){
	int ans=0;
	if(a&0xffff0000){
		ans+=16;
		a>>=16;
	}
	if(a&0x0000ff00){
		ans+=8;
		a>>=8;
	}
	if(a&0x000000f0){
		ans+=4;
		a>>=4;
	}
	if(a&0x0000000c){
		ans+=2;
		a>>=2;
	}
	if(a&0x00000002){
		ans+=1;
		a>>=1;
	}
	return ans;
}
inline int read(){
	register int a=0,b=0;
	register char c;
	c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')b=1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		a*=10;
		a+=c-'0';
		c=getchar();
	}
	return b?-a:a;
}
const int MAXM = 100010;
const int MOD = 1e9 + 7;
struct Matrix{
	int n, m;
	int **data;
	Matrix(int e) : n(e), m(e){
		data = new int*[n + 1];
		rep(i, 0, n){
			data[i] = new int[m + 1];
		}
		rep(i, 1, n){
			data[i][i] = 1;
		}
	}
	Matrix(int n, int m) : n(n), m(m){
		data = new int*[n + 1];
		rep(i, 0, n){
			data[i] = new int[m + 1];
		}
	}
	Matrix(const Matrix & other) : n(other.n), m(other.m){
		data = new int*[n + 1];
		rep(i, 0, n){
			data[i] = new int[m + 1];
		}
		rep(i, 1, n){
			rep(j, 1, m){
				data[i][j] = other.data[i][j];
			}
		}
	}
	~Matrix(){
		rep(i, 0, n){
			delete[] data[i];
		}
		delete[] data;
	}
	Matrix& operator= (const Matrix & other){
		if(&other == this) return *this;
		rep(i, 0, n){
			delete[] data[i];
		}
		delete[] data;
		n = other.n;
		m = other.m;
		data = new int*[n + 1];
		rep(i, 0, n){
			data[i] = new int[m + 1];
		}
		rep(i, 1, n){
			rep(j, 1, m){
				data[i][j] = other.data[i][j];
			}
		}
		return *this;
	}
	Matrix operator* (const Matrix &other){
		Matrix ans(n, other.m);
//		ans.n = n;
//		ans.m = other.m;
		rep(i, 1, ans.n){
			rep(j, 1, ans.m){
				ans.data[i][j] = 0;
				rep(k, 1, m){
					ans.data[i][j] = ((ll)ans.data[i][j] + (ll)data[i][k] * other.data[k][j] % MOD) % MOD;
					if(ans.data[i][j] < 0){
						cout << 1;
					}
				}
			}
		}
		return ans;
	}
};
Matrix ksm(Matrix a, int k){
	if(k == 0) return Matrix(a.n);
	if(k == 1) return a;
	if(k & 1){
		Matrix tmp = ksm(a, k >> 1);
		return tmp * tmp * a;
	}
	else{
		Matrix tmp = ksm(a, k >> 1);
		return tmp * tmp;
	}
}
int s[MAXM], l[MAXM];
signed main(){
	int m = read(), n = read();
	rep(i, 1, m) s[i] = read();
	rep(i, 1, m) l[i] = read();
	Matrix A(m, 2), B(2, m);
	rep(i, 1, m){
		A.data[i][1] = s[i] + l[i];
		A.data[i][2] = l[i];
	}
	rep(i, 1, m){
		B.data[1][i] = s[i] + l[i];
		B.data[2][i] = MOD - l[i];
	}
	Matrix a0(m, 1);
	rep(i, 2, m) a0.data[i][1] = 0;
	a0.data[1][1] = 1;
	Matrix tmp = ksm(B * A, n - 1) * B * a0;
	Matrix ans = A * tmp;
	ll sum = 0;
	rep(i, 1, m) sum += ans.data[i][1];
	printf("%lld", sum % MOD);
    return 0;
}
数学 > 矩阵
CF1970E3-Trails (Hard)
http://yoursite.com/2024/05/15/CF1970E3-Trails-Hard/
作者
99_wood
发布于
2024年5月15日
许可协议