CF1152F2 Neko Rules the Catniverse (Large Version) 题解（插入类dp，状压，矩阵乘法，dp技巧）

题目

原题连接

简要题意：

给定参数$n$，$k$，$m$，你需要求出有多少个大小为 $k$ 的序列 $a$ 满足如下三个条件：

1. 任意两个元素其权值不同。
2. 对于任意 $i$ 满足 $1\le i\le k$ 有 $1\le a_i\le n$。
3. 对于任意 $i$ 满足 $2\le i\le k$ 有 $a_i\le a_{i-1}+m$。

答案对 $10^9+7$ 取模。

数据规模：
$1\le n\le 10^9$， $1\le k\le \min (n,12)$， $1\le m\le 4$。

分析

注意到 $n$ 很大，但是 $k,m$ 都比较小。考虑以 $n$ 作为阶段$dp$。

有一个垃圾的想法：设 $d{p}_{i,msk}$ 表示考虑了前 $i$ 个数，其中 $msk$ 是 $1$ 的位置上已经选出了数字的方案数。
那么转移就是对于当前数，考虑把哪一个位置填上这个数，或者不用这个数。
设枚举的位置为 $p$，发现将当前数填到 $p$ 后序列仍然合法的限制只有 $a_p\le a_{p-1}+m$。如果 $p-1$ 此时还没有填数，那么就没有限制。如果已经填了该怎么办？
那么我们需要记录所有已经填过的位置上的数字与当前数字的差。如果这个差大于 $m$，直接标记 $-1$ 代表不能再往这个位置后面填数了。这样复杂度为 $O(n\times m^k)$。显然加速阶段也过不了。

考虑从小到大枚举数 $x$ 并讨论它是否要插入到序列中。
那么我们会发现 $x$ 能插入的位置只有 $[x-1,x-m]$ 的后面或者第一个位置。只需要用一个 $m$ 位的二进制数字记录 $[x-1,x-m]$ 哪些已经在序列中就可以求出转移系数。并且每一种插法最后一定唯一对应一种合法序列，而最终的一个合法序列一定唯一对应一种插法。这是一个双射因此方案数不重不漏。

那么 $dp$ 状态变成了 $d{p}_{i,j,msk}$ 表示已经考虑了$[1,i]$，当前序列中有 $j$ 个数字。 $[i-m+1,i]$ 在序列中的出现情况是 $msk$ 的方案数。

转移动为：

• $d{p}_{i,j,msk}\times (cn{t}_{msk}+1)\to d{p}_{i+1,j+1,(msk>>1)|(1<<(m-1))}$
• $d{p}_{i,j,mks}\to d{p}_{i+1,j,msk>>1}$

第一个代表选 $i+1$，第二个代表不选。
发现转移和 $i$ 无关，而 $(j,msk)$ 的总状态数为 $(k+1)\times 2^m\le 208$。因此矩阵加速即可。

时间复杂度 $O({\log }_{2}n\times ((k+1)\times 2^m{)}^3)$。
CODE：

#include<bits/stdc++.h>
using namespace std;
const int N = 210;
typedef long long LL;
const LL mod = 1e9 + 7;
struct matrix {
	LL mt[N][N];
	friend matrix operator * (matrix a, matrix b) {
		matrix c; memset(c.mt, 0, sizeof c.mt);
		for(int i = 0; i < N; i ++ ) 
		    for(int j = 0; j < N; j ++ ) 
		        for(int k = 0; k < N; k ++ )
		            c.mt[i][j] = (c.mt[i][j] + a.mt[i][k] * b.mt[k][j] % mod) % mod;
		return c;
	}
};
matrix Mat; // 转移矩阵 
int n, k, m;
int cnt[1 << 4];
int idx[15][1 << 4], rk;
matrix Pow(matrix x, int y) {
	matrix res; matrix k = x;
	for(int i = 0; i < N; i ++ ) 
	    for(int j = 0; j < N; j ++ ) 
	   	    res.mt[i][j] = (i == j); 	
	while(y) {
		if(y & 1) res = res * k;
		y >>= 1;
		k = k * k;
	}
	return res;
}
int main() {
	cin >> n >> k >> m;
	for(int i = 0; i < (1 << 4); i ++ ) cnt[i] = cnt[i >> 1] + (i & 1);
	for(int i = 0; i <= k; i ++ ) 
	    for(int j = 0; j < (1 << m); j ++ )
	        idx[i][j] = ++ rk;
	for(int i = 0; i <= k; i ++ ) {
		for(int j = 0; j < (1 << m); j ++ ) {
			if(i < k) {
				int p = idx[i][j];
				int q = idx[i + 1][(j >> 1) | (1 << (m - 1))];
				Mat.mt[p][q] = 1LL * (cnt[j] + 1);
			}
			int p = idx[i][j];
			int q = idx[i][j >> 1];
			Mat.mt[p][q] = 1;
		}
	}
	matrix f; f.mt[0][idx[0][0]] = 1;
	f = f * Pow(Mat, n);
	LL res = 0;
	for(int j = 0; j < (1 << m); j ++ ) res = (res + f.mt[0][idx[k][j]]) % mod;
	printf("%lld\n", res);
	return 0;
}