题解：CF1895F Fancy Arrays

· · 题解

题意就是让你求出有多少个长度为 n 的数组，使得相邻两个数相差不超过 k，并且至少有一个数属于 [x,x+k-1]。

我们先看“并且至少有一个数属于 [x,x+k-1]”这一条件，需要满足这一条件，就需要同时满 \max_{i=1}^na_i\ge x 且 \min_{i=1}^{n}a_i\le x+k-1。

用容斥原理转化一下，我们就可以，用 \min_{i=1}^{n}a_i\le x+k-1 的方案总数减去 \max_{i=1}^na_i\lt x 的方案总数。

(I) 看 \min_{i=1}^{n}a_i\le x+k-1 的方案总数如何求

我们发现只要确定了 \min_{i=1}^{n}a_i 和 a 的差分数组 c，就可以唯一确定数组 a。

因为 \min_{i=1}^{n}a_i 要小于等于 x+k-1 这个区间中所以有 x+k 中方案选择。因为 \forall c_i 都需要在区间 [-k,k] 中 (c_i\le k)，所以有 2k+1 种选择，差分数组上有 n-1 个位置，所以有 (2k+1)^{n-1} 种选择。根据简单的配列组合知识，就可以得到第一部分的总方案数是 (x+k)\times (2k+1)^{n-1}。

(II) 看 \max_{i=1}^na_i< x 的方案总数如何求

后者就是要求出 \forall a_i\in [0,x) 的方案数。可以发现可以用 DP 求出。

令 f_{i,j} 表示 a_i=j 的总方案个数。可以得到转移方程 f_{i,j}=\sum_{t=j-k}^{j+k}f_{i-1,t}。但是题目 n 的数据范围太大并且 x 的范围很小。又发现 f 的转移式恒定不变，考虑矩阵快速幂优化，具体方法如下：

定义初始一个 1\times x 的矩阵 \text{F} 以及一个 x\times x 转移矩阵 \text{G}，其中 \text{F} 的初始值都是 1，\text{G} 的初始值若 |i-j|\le k 则令 G_{i,j}=1，最后求 n 次幂即可。

得到了两部分的答案，减一下就可以了，时间复杂度 O(x^3\log_{2}n)。

代码：

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int maxn = 40 + 5, mod = 1e9 + 7;

int n, x, k;

struct Matrix{
    int a[maxn][maxn];
    friend Matrix operator * (const Matrix &u, const Matrix &v) {
        Matrix res;
        memset(res.a, 0, sizeof res.a);
        for (int k = 1; k <= x; ++k) 
            for (int i = 1; i <= x; ++i) 
                for (int j = 1; j <= x; ++j) 
                    res.a[i][j] = (res.a[i][j] + u.a[i][k] * v.a[k][j]) % mod;
        return res;
    }
} r1, r2;

int qpow(int a, int b) {
    int res = 1;
    while (b) {
        if  (b & 1) res = res * a % mod;
        b >>= 1, a = a * a % mod;
    }
    return res;
}

void mpow(int k) {
    while (k) {
        if (k & 1) r1 = r1 * r2; 
        r2 = r2 * r2, k >>= 1;
    }
}

void solve() {
    cin >> n >> x >> k;
    int ans = qpow(2 * k + 1, n - 1) * (x + k) % mod;
    for (int i = 1; i <= x; ++i) r1.a[1][i] = 1;
    for (int i = 1; i <= x; ++i) for (int j = 1; j <= x; ++j) r2.a[i][j] = (abs(i - j) <= k);
    mpow(n - 1);
    for (int i = 1; i <= x; ++i) ans = (ans - r1.a[1][i] + mod) % mod;
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
}