西陆军事新闻最新消息_广州正佳广场封闭_裤子seo关键词_个人网页模板

题目

原题连接

简要题意：

给定参数$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;
}