k进制下处理线性代数问题：2026暑杭电 1012

1012 向量

我们原先要处理的式子是：

u=(I+kA)v=v+kAvu−v=kAvu=(I+kA)v=v+kAv\\ u-v=kAv

我们接下来在 kk 进制下求解 vv

为了方便理解，我们可以令 k=10k=10

不妨记：v=v0v1‾v=\overline{v_0v_1}，其实 v1v_1 是个位数，v0v_0 是剩余位数。

显然有

u0−v0≡0(modk)u_0-v_0\equiv 0\pmod k

然后我们就可以求出 v0v_0 了。

接下来我们要求十位了，我们只需要把最上面的式子中的所有个位数去掉就可以了！也就是把所有数右移一位，所有十位数变成个位数。

u0u1‾−v0v1‾=kAv0v1‾u0u1‾−v0v1‾=kA(v0‾×k+v1‾)u0u1‾−v0v1‾=k2A⋅v0‾+kA⋅v1‾u0−v0=kAv0+Av1(u0−Av1)−v0=kAv0\begin{align*} \overline{u_0u_1}-\overline{v_0v_1}&=kA\overline{v_0v_1}\\ \overline{u_0u_1}-\overline{v_0v_1}&=kA(\overline{v_0}\times k+\overline{v_1})\\ \overline{u_0u_1}-\overline{v_0v_1}&=k^2A\cdot \overline{v_0}+kA\cdot\overline{v_1}\\ u_0-v_0&=kAv_0+Av_1\\ (u_0-Av_1)-v_0&=kAv_0 \end{align*}

因此我们就可以愉快地递归下去了

image-20260722231223332

一些实现细节（也是我不能完全理解透的地方但勉强在解释）：

  1. 最后不用判断 u[i]u[i] 是否全部位0，因为负数在模意义下一定是无限循环
  2. kpk^p 上限设到 2e92e9，如果大了出来就把它减了
  3. 在运算过程中，要始终保持 v[i]v[i] 为正，通过模意义进行转换
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
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) 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
//#define mo
#define N 1000010
int n, m, i, j, k, T;
int u[N], x[N], R[N], v[N], U[N]; 
vector<int>a[N]; 
int r, pw, flg; 

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
	T = read();
	while(T--) {
		n = read(); k = read(); m = read(); 
		for(i = 1; i <= n; ++i) u[i] = U[i] = read(); 
		for(i = 1; i <= n; ++i) v[i] = 0; 
		for(i = 1; i <= n; ++i) a[i].clear(); 
		for(i = 1; i <= m; ++i) x[i] = read();  
		for(i = 1; i <= m; ++i) a[x[i]].pb(read());  
		for(r = pw = 1, flg = 0; pw <= 2e9 ; ++r) {
			debug("u : "); for(i = 1; i <= n; ++i) debug("%lld ", u[i]); debug("\n"); 
			for(i = 1; i <= n; ++i) {
				R[i] = u[i] % k; 
				if(R[i] < 0) R[i] = R[i] + k; 
				v[i] += R[i] * pw; 
			}
			debug("v : "); for(i = 1; i <= n; ++i) debug("%lld ", R[i]); debug("\n"); 
			if(i <= n) { flg = 1; break; }
			for(i = 1; i <= n; ++i) {
				u[i] = (u[i] - R[i]) / k; 
			}
			for(i = 1; i <= n; ++i) {
				for(auto A : a[i]) u[i] -= R[A]; 
			}
			pw = pw * k; 
			
		}
		if(flg == 1) {
//			debug("%lld\n", r); 
			printf("No Solution\n"); 
			continue; 
		}
//		for(i = 1; i <= n; ++i) if(u[i]) break; 
//		if(i <= n) {
//			printf("No Solution\n"); 
//			continue; 
//		}
		for(i = 1; i <= n; ++i) {
			if(v[i] > 1e9) v[i] -= pw; 
		}
		for(i = 1; i <= n; ++i) 
			if(v[i] < -1e9 || v[i] > 1e9) break; 
		if(i <= n) {
			printf("No Solution\n"); 
			continue;
		}
		for(i = 1; i <= n; ++i) {
			int sx = 0; 
			for(auto A : a[i]) sx += v[A] * k; 
			if(sx + v[i] != U[i]) break; 
		}
		if(i <= n) {
			printf("No Solution\n"); 
			continue;
		}
		for(i = 1; i <= n; ++i) printf("%lld ", v[i]); printf("\n"); 
	}

	return 0;
}