CF1152F2 Neko Rules the Catniverse (Large Version)
题解
考虑 DP 维护访问路径,但是正着做会出现问题:现在的 i 在 [1,i−1] 的前驱无法确定,即 1≤y≤x+m 的限制只对上界有效,考虑把坐标倒过来,把限制移到下界。
具体的,原本坐标为 1≤y≤x+m,变化后为 x−m≤y≤n,这样我们向右跳到未处理的部分无限制,往回跳最多 m。
注意,这里坐标的变换只是转换题目条件,前后问题相互等价。
现在考虑 DP,设 f[i][j][S] 表示已经考虑完第 i 个星球,选择了 j 个星球,在 [i−m+1,i] 中星球选择情况为 S。
接下来我们以是否选择第 i+1 个星球进行转移:
第 i+1 个星球不选,新的 S′ 只需要去掉 i−m+1 这一位,加上 i+1 的 0 即可,转移到 f[i+1][j][S′]。
第 i+1 个星球选,接下来又有两种情况:
- 放在访问路径的最后,显然是合法的,因为 i+1 的编号比前面的大(别忘了转换后的限制条件),共有 1 种。
- 放在之前路径里面,由于 x−m≤y 的限制,i+1 一定只能被放在 [i+1−m,i] 之间,这部分的选择情况已经存在 S 里了,即我们要将其插入到 S 中一个 1 之前,共有 popcount(S)+1 种。
综合起来,将贡献转移到 f[i+1][j+1][S′′],其中 S′′ 是 S 去掉 i−m+1 这一位,将 i+1 置为 1 得到的。
现在我们有了转移方程,但是直接转移复杂度是 O(n⋅(k+1)3⋅8m),无法通过,考虑优化。
不难发现,我们的状态实际上跟 i 没啥关系,只跟 j,S 有直接关系,所以我们考虑矩阵快速幂优化,我们要把转移写成矩阵的形式。
我们需要把 j,S 所有可能取值数,共 D=(k+1)×2m=208 种,我们给其一个对应关系 w(i,S) 表示其在答案矩阵 F 中对应坐标。
所以转移应该形如 Fi+1=T×Fi,显然转移矩阵 T 应为 D×D 的矩阵,其中某一 T[x][y] 应该表示从旧状态 y 转移到新状态 x 增加的方案,所以我们只需要枚举旧状态 y,根据选和不选的权值推出新状态 x,再将 T[x][y] 加上贡献即可。
至于统计答案,显然 F0 中 F0[w(0,0)]=1,其余为 0,最终答案矩阵即为 Fn=T×F0,答案是 Fn 中所有 j=k 的方案数之和。
最终时间复杂度为 O((k+1)3⋅8m⋅logn),可以通过。
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
struct Matrix {
static const int M = 208;
ll mat[M][M];
Matrix() {
for(int i = 0 ; i < M ; i ++)
for(int j = 0 ; j < M ; j ++)
mat[i][j] = 0;
}
void initI() {
for(int i = 0 ; i < M ; i ++)
mat[i][i] = 1;
}
Matrix operator* (const Matrix &W) const {
Matrix res;
for(int i = 0 ; i < M ; i ++)
for(int j = 0 ; j < M ; j ++)
for(int k = 0 ; k < M ; k ++) {
res.mat[i][j] = (res.mat[i][j] +
mat[i][k]*W.mat[k][j]%MOD) % MOD;
}
return res;
}
};
ll n; int k , m;
int w(int j , int S) {
return j*(1<<m) + S;
}
int popcount(int S) {
int res = 0;
while(S) res ++ , S -= S&(-S);
return res;
}
int main() {
scanf("%lld%d%d" , &n , &k , &m);
Matrix T , F;
F.mat[w(0,0)][0] = 1;
for(int j = 0 ; j <= k ; j ++) {
for(int S = 0 ; S < (1<<m) ; S ++) {
int S1 = (S<<1) & ((1<<m)-1);
T.mat[w(j,S1)][w(j,S)] ++;
if(j < k) {
int S2 = S1|1;
T.mat[w(j+1,S2)][w(j,S)] += popcount(S)+1;
}
}
}
while(n) {
if(n & 1) F = T * F;
T = T * T; n >>= 1;
}
ll res = 0;
for(int S = 0 ; S < (1<<m) ; S ++)
res = (res + F.mat[w(k,S)][0]) % MOD;
printf("%lld\n" , res);
return 0;
}