跳至主要內容

[Medium] CF1895F Fancy Arrays

xiezheyuan2025/2/10做题笔记组合计数dp容斥约 938 字大约 5 分钟

简要题意

给定参数 x,kx,k，定义一个长度为 nn 的序列 aa 是好的，当且仅当满足下面所有条件：

  • ai∈Na_i\in\mathbb{N}。
  • ∃i∈[1,n],ai∈[x,x+k−1]\exist i\in[1,n],a_i\in[x,x+k-1]。
  • ∀i∈[2,n],∣ai−ai−1∣≤k\forall i\in[2,n],|a_i-a_{i-1}|\leq k。

你需要计算好的序列数量，答案对 109+710^9+7 取模。

TT 组数据。1≤n,k≤109,0≤x≤40,1≤T≤501\leq n,k\leq 10^9,0\leq x\leq 40,1\leq T\leq 50。

思路

Part 1

首先最难考虑的限制就是 ∃i∈[1,n],ai∈[x,x+k−1]\exist i\in[1,n],a_i\in[x,x+k-1]，我们将其转换为两条限制：

  • max⁡ai≥x\max a_i\geq x。
  • min⁡ai≤x+k−1\min a_i\leq x+k-1。

容易发现，假如我们可以同时满足这两条限制，则等价于满足原本的第二条限制。

然后我们发现“同时”也是难以考虑到，不妨容斥。改为求满足第二个条件的数量，减去不满足第一个条件的数量。

Part 2

min⁡ai≤x+k−1\min a_i\leq x+k-1。

考虑原本的第三条限制 ∀i∈[2,n],∣ai−ai−1∣≤k\forall i\in[2,n],|a_i-a_{i-1}|\leq k，那么取 b=Δab=\Delta a 即 aa 的差分数组，则 bi∈[−k,k]b_i\in[-k,k]。

考虑如何在差分数组上体现出 min⁡\min，意料之中的是 min⁡\min 在差分数组中无法体现，并且 min⁡\min 信息与差分数组是完全独立的，通过这两个信息可以还原 aa（方法就是对 Δa\Delta a 求前缀和，选取最小值，然后加上 min⁡\min 和前缀和最小值的差，并补充第一项）。

于是计数就非常简单了，最小值数量是 ∣[0,x+k−1]∣=x+k|[0,x+k-1]|=x+k，差分数组的数量是 (∣[−k,k]∣)n−1=(2k+1)n−1(|[-k,k]|)^{n-1}=(2k+1)^{n-1}，于是这一部分的答案是：

(x+k)(2k+1)n−1\boxed{(x+k)(2k+1)^{n-1}}

这一部分时间复杂度 O(Tlog⁡n)O(T\log n)，并不是本题的复杂度瓶颈。

Part 3

max⁡ai<x\max a_i<x。

最大值小于 xx，差分数组的每一项位于 [−k,k][-k,k]，求序列数量。这是经典的 dp 问题，设 f(i,j)f(i,j) 表示前 ii 个数，最后一项为 jj 的方案数，不难有转移：

f(i,j)=[0≤j<x]∑t=j−kj+kf(i−1,t)\boxed{f(i,j)=[0\leq j<x]\sum_{t=j-k}^{j+k}f(i-1,t)}

初值 f(1,i)=[0≤i<x]f(1,i)=[0\leq i<x] 表示第一个数没有特别的限制。

这个 dp 时间复杂度 O(nx2)O(nx^2) 无法承受，不过这个转移是加法线性组合的形式，可以考虑矩阵快速幂优化，这是容易的。

时间复杂度 O(Tx3log⁡n)O(Tx^3\log n)。

代码

#include <bits/stdc++.h>
using namespace std;

constexpr int mod = 1e9 + 7;
int Add(int x, int y){ return (x + y) >= mod ? (x + y - mod) : (x + y); }
int Sub(int x, int y){ return (x - y) < 0 ? (x - y + mod) : (x - y); }
int Mul(int x, int y){ return 1ll * x * y % mod; }

int fastpow(int x, int y){
    int ret = 1;
    for(;y;y>>=1,x=Mul(x, x)){ if(y & 1) ret = Mul(ret, x); }
    return ret;
}

int n, x, k;

struct matrix{
    int a[45][45], n, m;
    int* operator[](int i){ return a[i]; }
    matrix(){ memset(a, 0, sizeof(a)); }
};

matrix operator*(matrix a, matrix b){
    matrix ret; ret.n = a.n, ret.m = b.m;
    for(int i=0;i<a.n;i++){
        for(int k=0;k<a.m;k++){
            for(int j=0;j<b.m;j++) ret[i][j] = Add(ret[i][j], Mul(a[i][k], b[k][j]));
        }
    }
    return ret;
}

matrix fastpow(matrix a, int b){
    matrix ret; ret.n = ret.m = a.n;
    for(int i=0;i<a.n;i++) ret[i][i] = 1;
    while(b){
        if(b & 1) ret = ret * a;
        a = a * a, b >>= 1;
    }
    return ret;
}

void solve(){
    cin >> n >> x >> k;
    matrix mat; mat.n = mat.m = x;
    for(int i=0;i<x;i++){
        for(int j=max(i-k,0);j<=min(i+k,x);j++) mat[j][i] = 1;
    }
    matrix ret; ret.n = 1, ret.m = x;
    for(int i=0;i<x;i++) ret[0][i] = 1;
    ret = ret * fastpow(mat, n - 1);
    int ans = 0;
    for(int i=0;i<x;i++) ans = Add(ans, ret[0][i]);
    ans = Sub(Mul(fastpow(Add(Add(k, k), 1), n - 1), Add(x, k)), ans);
    cout << ans << '\n';
}

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

// Written by xiezheyuan