COI 2020 Semafor（矩阵乘法+优化）

COI 2020 Semafor

题目大意

• 给定一个初始显示$X$的$M$位的五段显示器，求$N$次操作后显示为$i(i\in [0,10^M))$的方案数，需满足每$K$次操作后显示的均是一个合法的数字。每次操作即改变显示器某一段的开关状态。
• $M\le 2，N\le 10^{15}$

题解

• 看到多次操作后求方案数会想到矩乘，为了满足$K$的限制，可以先把每操作$K$次后的状态计算出来，如果不是合法的数的状态则忽略，再计算$\frac{N}{K}$ 次合法的数之间的转移，最后再算上剩下$N\mathrm{mod}K$ 次操作。
• 计算一下复杂度，合法的数之间的转移最大是${10^2}^3\ast \log N=10^6\ast \log N$，但前面每$K$次所有状态之间的转移，当$M=2$时显示器有十段，状态压缩后大小为$2^{10}=1024$，矩乘转移的复杂度一次就是$(2^{10}{)}^3=2^{30}$，显然需要改变做法。
• 可以发现，当合法的两个数$x,y$之间的转移，相当于把某些位取反，而剩下的不变，即异或上某数$k=x\mathrm{xor}y$。那么对固定的$k$，任意$x$转移到$x\mathrm{xor}k$的方案数都相等，所以转移矩阵就不需要维护$2^{10}\ast 2^{10}$大小，而只需记录不同的转移$k$的值。
• 转移时直接枚举$i$和$j$转移到$i\mathrm{xor}j$即可。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define md 1000000007
#define N 1100
#define M 110
int p[10] = {10, 2, 9, 7, 18, 21, 12, 3, 29, 23};
int vi[N];
ll d[M], ans[M];
ll f[M][M], g[M][M], c[M][M], cc[M][M];
ll F[N], G[N], C[N];
void ksm(ll x, int n) {
	if(!x) {
		for(int i = 0; i < n; i++)	
			for(int j = 0; j < n; j++) f[i][j] = (i == j);
	}
	else {
		ksm(x / 2, n);
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++) g[i][j] = 0;
		for(int i = 0; i < n; i++)
			for(int k = 0; k < n; k++) if(f[i][k])
				for(int j = 0; j < n; j++) g[i][j] = (g[i][j] + f[i][k] * f[k][j]) % md;
		for(int i = 0; i < n; i++)				
			for(int j = 0; j < n; j++) f[i][j] = g[i][j];
		if(x % 2) {
			for(int i = 0; i < n; i++)
				for(int j = 0; j < n; j++) g[i][j] = 0;
			for(int i = 0; i < n; i++)
				for(int k = 0; k < n; k++) if(c[i][k])
					for(int j = 0; j < n; j++) g[i][j] = (g[i][j] + c[i][k] * f[k][j]) % md;
			for(int i = 0; i < n; i++)				
				for(int j = 0; j < n; j++) f[i][j] = g[i][j];
		}
	}
}
void Ksm(ll x, int n) {
	if(!x) {
		for(int i = 0; i < n; i++) F[i] = (i == 0);
	}
	else {
		Ksm(x / 2, n);
		for(int i = 0; i < n; i++) G[i] = 0;
		for(int i = 0; i < n; i++) if(F[i])
			for(int j = 0; j < n; j++) G[i ^ j] = (G[i ^ j] + F[i] * F[j]) % md;
		for(int i = 0; i < n; i++) F[i] = G[i];
		if(x % 2) {
			for(int i = 0; i < n; i++) G[i] = 0;
			for(int i = 0; i < n; i++) if(C[i])
				for(int j = 0; j < n; j++) G[i ^ j] = (G[i ^ j] + C[i] * F[j]) % md;
			for(int i = 0; i < n; i++) F[i] = G[i];
		}
	}
}
int main() {
	ll n, K;
	int m, X, i, j, k;
	scanf("%d%lld%lld%d", &m, &n, &K, &X);
	if(m == 1) {
		for(i = 0; i < 5; i++) C[1 << i] = 1;
		Ksm(K, 32);
		memset(vi, 255, sizeof(vi));
		for(i = 0; i < 10; i++) vi[p[i]] = i;
		for(i = 0; i < 32; i++) if(vi[i] >= 0) 
			for(j = 0; j < 32; j++) if(vi[j] >= 0) c[vi[i]][vi[j]] = F[i ^ j];
		ksm(n / K, 10);
		for(i = 0; i < 10; i++) d[i] = f[X][i];
		Ksm(n % K, 32);
		for(i = 0; i < 10; i++) 
			for(j = 0; j < 10; j++) ans[j] = (ans[j] + d[i] * F[p[i] ^ p[j]]) % md;
		for(i = 0; i < 10; i++) printf("%lld
", ans[i]);
	}
	else {
		for(i = 0; i < 10; i++) C[1 << i] = 1;
		Ksm(K, 1024);
		memset(vi, 255, sizeof(vi));
		for(i = 0; i < 10; i++) 
			for(j = 0; j < 10; j++) vi[p[i] * 32 + p[j]] = i * 10 + j;
		for(i = 0; i < 1024; i++) if(vi[i] >= 0) 
			for(j = 0; j < 1024; j++) if(vi[j] >= 0) c[vi[i]][vi[j]] = F[i ^ j];
		ksm(n / K, 100);
		for(i = 0; i < 100; i++) d[i] = f[X][i];
		Ksm(n % K, 1024);
		for(i = 0; i < 100; i++) 
			for(j = 0; j < 100; j++) ans[j] = (ans[j] + d[i] * F[(p[i / 10] * 32 + p[i % 10]) ^ (p[j / 10] * 32 + p[j % 10])]) % md;
		for(i = 0; i < 100; i++) printf("%lld
", ans[i]);
	} 
	return 0;
}