CF1895F

Lightwhite · 2023-11-06 00:58:30 · 题解

portal

题意：求存在多少个长度为 n 的序列 a 使相邻两数差不超过 k，且数列中存在至少一个数在区间 [x, x + k - 1] 内。1\leq n, k\leq 10^9, 0\leq x\leq 40。

注意到假设我们确定了差分数组和最小值，就可以得到整个序列的具体值。这是显然的，因为差分数组可以前缀和回去得到所有元素和 a_1 的差，又知道最小值就可以推出全部。同时，两个序列如果差分序列或最小值不同，两者显然不同。

于是我们可以试求 \min\limits_{1\leq i\leq n}a_i \leq x+k-1 且 |a_i-a_{i+1}| 的不同序列个数。发现存在 (2k+1)^{n-1} 种不同的差分序列和 x+k 种最小值满足条件。只需要再除去 \max\limits_{1\leq i\leq n}a_i<x 的方案数即可。

发现这个东西很可 dp。由于序列中数的值域仅为 [0, x)，因此直接设 f_{i, j} 表示当前在第 i 位，且 a_i = j 的方案数量，暴力转移实在不可接受。但是由于相邻两数差不超过 k 是当前唯一的限制，直接矩阵快速幂优化即可。时间复杂度 O(x^3\log n)。

// STOOOOOOOOOOOOOOOOOOOOOOOOO hzt CCCCCCCCCCCCCCCCCCCCCCCORZ
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;
using LL = long long;
using PII = pair<int, int>;
constexpr int kX = 40 + 1, kP = 1e9 + 7;

int T;
int n, x, k;

struct Mat {
  int a[kX][kX];
  Mat() { fill(a[0], a[x] + x + 1, 0); }
  Mat operator*(const Mat &o) const {
    Mat ret;
    for (int i = 0; i < x; i++) {
      for (int k = 0; k < x; k++) {
        for (int j = 0; j < x; j++) {
          ret.a[i][j] = (ret.a[i][j] + 1ll * a[i][k] * o.a[k][j]) % kP;
        }
      }
    }
    return ret;
  }
} a, ret;
int P(int a, int b) {
  int ret = 1;
  for (; b > 0; b /= 2) {
    if (b & 1) {
      ret = 1ll * ret * a % kP;
    }
    a = 1ll * a * a % kP;
  }
  return ret;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> T;
  while (T--) {
    cin >> n >> x >> k;
    int ans = 1ll * P(2 * k + 1, n - 1) * (x + k) % kP;
    for (int i = 0; i < x; i++) {
      for (int j = 0; j < x; j++) {
        a.a[i][j] = (abs(i - j) <= k);
      }
    }
    ret = Mat();
    int b = n - 1;
    for (int i = 0; i < x; i++) {
      ret.a[0][i] = 1;
    }
    for (; b > 0; b /= 2) {
      if (b & 1) {
        ret = ret * a;
      }
      a = a * a;
    }
    for (int i = 0; i < x; i++) {
      ans = (ans - ret.a[0][i] + kP) % kP;
    }
    cout << ans << '\n';
  }
  return 0;
}