8.20T3 无损加密（线性代数转LGV+状压dp+高维前缀和）

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141373559

http://cplusoj.com/d/senior/p/NODSX2301C

对于式子：

在这里插入图片描述

这个神秘的线性代数形式比较难处理，但我们可以考虑其组合意义。行列式现存的可用组合意义之一就是LGV（矩阵式不太可用）

先把原先的矩阵转化为一个有向图。现在我们要构造一个图，满足 Bi,jB_{i,j} 代表从 aia_i 走到 bjb_j 所有路径权值积的和为 Bi,jB_{i,j} ，而上面行列式求的就是从 a1→na_{1\to n} 走到 bb 的任意 (mn)\binom m n 个点的不想交路劲数。

现在我们已经理清条件，考虑构造图了。我们先弄一行 aa 和 bb ，

在这里插入图片描述

现在是满足条件的。

我们考虑在 [l,r][l,r] 内加入 d,cd,c ，不妨令其为 [2,3][2,3] ，在外面加没问题：

在这里插入图片描述

而对于 [l,r] 内的情况，我们相当于在原先基础上多了一个不断往右增 cc 的边：

在这里插入图片描述

这样子建边能完美解决我们的问题。

现在只需要对最终的图统计不相交路径数即可。

我们考虑第 ii 列的链：

在这里插入图片描述

根据题目，这条链的总入度和总出度不超过 ss ，其实我们状压一下。

我们可以先钦定哪些入度有流，从上一步的 f[S]f[S] 转移过来，当然必须满足红色点也有流。

然后我们直接让这些流先走到最近的出度。

当走到最近的出度后，他们还可以往下走，此时我们可以拿一个类似高维前缀和的东西来实现。而这里，我们要按顺序，先走最上面，再往下一个一个考虑，那样子才能保证路径不交。

我们可以设 g(s,i)g(s,i) 表示当前状态是 ss ，考虑到第 ii 个1的路径权值积之和、

最后我们把黄色点的东西去掉，就可以转移到新 f[T]f[T] 了

答案为 f[0]f[0]

复杂度我实现有点劣，为 O(n2ss2)O(n2^s s^2) ，但很多情况会直接停止，所以跑不满。

4k

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
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
 #define debag(...) fprintf(stderr, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
 #define debag(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
#define M 9
#define mo (int)(1e9 + 7)
#define N 200010
int pw(int a, int b) {
	int ans = 1; 
	while(b) {
		if(b & 1) ans *= a; 
		a *= a; b >>= 1; 
		ans %= mo; a %= mo; 
	}
	return ans; 
}
int pw(int a) { return pw(a, mo - 2); }
inline void Mod(int &a) { if(a >= mo || a <= -mo) a %= mo; if(a < 0) a += mo; }
inline void Add(int &a, int b) { a += b; Mod(a); }
inline void Mul(int &a, int b) { Mod(b); a *= b; Mod(a); } 
int n, m, i, j, k, T;
int C[N * M], D[N * M], q, l, r, Ds[N * M]; 
vector<int>L[N], R[N]; 
int nl, nr, s, t, f[1 << 10], g[1 << 10][11], nxt[15]; 
int ans, c[15], d[15], del[15]; 

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}
	n = read(); m = read(); q = read(); Ds[0] = C[q + 1] = 1; 
	for(T = 1; T <= q; ++T) {
		l = read(); r = read(); C[T] = read(); D[T] = read(); 
		Ds[T] = D[T] * Ds[T - 1] % mo; 
		for(j = l + 1; j <= r; ++j) L[j].pb(T); 
		for(j = l; j < r; ++j) R[j].pb(T); 
	}
	Ds[q + 1] = Ds[q]; 
	debug("Ds : "); for(i = 0; i <= q + 1; ++i) debug("%lld ", Ds[i]); debug("\n"); 
	f[0] = 1; 
	for(T = 1; T <= m; ++T) {
		nl = L[T].size(); j = 0; 
		R[T].pb(q + 1); nr = R[T].size(); 
		for(auto t : L[T]) debug("%lld ", t); debug("\n"); 
		for(auto t : R[T]) debug("%lld ", t); debug("\n"); 
		for(auto t : L[T]) {
			for(k = 0; k < nr; ++k) 
				if(R[T][k] >= t) break; 
			nxt[j] = k; del[j] = Ds[R[T][k]] * pw(Ds[t]) % mo; ++j; 
			debug("[%lld %lld]%lld ", t, R[T][k], nxt[j - 1]); 
		}
		debug("\n"); 
		memset(g, 0, sizeof(g)); 
		for(s = 0; s < (1 << nl); ++s) {
			debug("f[%lld] = %lld\n", s, f[s]); 
			t = (T <= n ? 1 : 0); 
			int G = (T <= n ? Ds[R[T][0]] : 1); 
			for(j = 0; j < nl; ++j) {
				if(!(s & (1 << j))) continue; 
				if(t & (1 << nxt[j])) break; 
				t |= (1 << nxt[j]); G = G * del[j] % mo; 
			}
			if(j < nl) continue; 
			debug("--> %lld[%lld %lld] += %lld\n", t, t, 1ll, f[s]); 
//			if(!t) Add(g[t][0], f[s]); 
//			else 
			Add(g[t][1], f[s] * G % mo); 
		}
		for(i = 0; i < nr; ++i) c[i] = C[R[T][i]]; 
		for(i = 0; i < nr - 1; ++i) d[i] = Ds[R[T][i + 1]] * pw(Ds[R[T][i]]) % mo; 
		debug("# C : "); for(i = 0; i < nr; ++i) debug("%lld ", c[i]); debug("\n"); 
		debug("# D : "); for(i = 0; i < nr - 1; ++i) debug("%lld ", d[i]); debug("\n"); 
		for(i = 1; i <= nl + 1; ++i) //第 
			for(s = 0; s < (1 << nr); ++s) {
//				debug("(%lld %lld)\n", s, i); 
				if(!g[s][i]) continue; 
				if(__builtin_popcount(s) < i) continue; 
				for(k = j = 0; k < nr; ++k) {
					if((s >> k) & 1) ++j; 
					if(j == i) break; 
				}
				debug("(%lld %lld)%lld * %lld [%lld] => (%lld %lld)\n", s, i, g[s][i], c[k], k, s, i + 1); 
				Add(g[s][i + 1], g[s][i] * c[k] % mo); 
				if(k + 1 >= nr || ((s >> k + 1) & 1)) continue; 
				t = s - (1 << k) + (1 << k + 1); 
				debug("(%lld %lld)%lld * %lld [%lld] => (%lld %lld)\n", s, i, g[s][i], d[k], k, t, i); 
				Add(g[t][i], g[s][i] * d[k] % mo); 
			}
		memset(f, 0, sizeof(f)); 
		for(s = 0; s < (1 << nr); ++s) {
			t = s & (1 << nr - 1) - 1; 
			int cnt = __builtin_popcount(s); 
			debug(">>> %lld ---> %lld (%lld %lld)[%lld]\n", s, t, s, cnt + 1, g[s][cnt + 1]); 
			Add(f[t], g[s][cnt + 1]); 
		}
		debug("------------\n"); 
	}
	ans = f[0]; 
	printf("%lld", ans); 
//	for(i = 1; i <= m; ++i) assert(L[i].size() <= 8 && R[i].size() <= 8); 
	return 0;
}