[CF1895F] Fancy Arrays

先把存在性容斥一下。变成 \([0,\infty]\) 减去 \([0,x-1]\) 和 \([x+k,\infty]\)。

\([0,x-1]\) 的答案显然可以矩阵快速幂 \(\mathcal O(x^3\log n)\) 求。考虑剩下两个。注意到两个单拎出来都不好求，所以直接求这两个的差。

注意到限制在于相邻项的差，于是我们去枚举差分数组，共有 \((2k+1)^{n-1}\) 种，然后考虑第一项，具体推导可以看八云蓝的题解，感性理解一下就是，\(p\) 在 \([0,\infty]\) 中的地位和 \(p+x+k\) 在 \([x+k,\infty]\) 中的地位是一样的，于是两者之差只有 \(x+k\) 项，于是答案就是 \((x+k)(2k+1)^{n-1}\)。时间复杂度 \(\mathcal O(Tx^3\log n)\)。

#include <bits/stdc++.h>
#define pb emplace_back
#define fir first
#define sec second

using i64 = long long;
using pii = std::pair<int, int>;

constexpr int maxn = 40 + 5;
constexpr int mod = 1e9 + 7;
void add(int& x, int y) { if ((x += y) >= mod) x -= mod; return ; }
void sub(int& x, int y) { if ((x -= y) < 0) x += mod; return ; }
int inc(int x, int y) { return (x + y) >= mod ? (x + y - mod) : (x + y); }
int dec(int x, int y) { return (x - y) < 0 ? (x - y + mod) : (x - y); }
int power(int x, int y) {
	int ans = 1;
	for (; y; y >>= 1, x = (i64)x * x % mod) if (y & 1) ans = (i64)ans * x % mod;
	return ans;
}
void chkmin(int& x, int y) { if (y < x) x = y; return ; }
void chkmax(int& x, int y) { if (y > x) x = y; return ; }
void chkmin(i64& x, i64 y) { if (y < x) x = y; return ; }
void chkmax(i64& x, i64 y) { if (y > x) x = y; return ; }
int n, k, x;

struct matrix {
	int g[maxn][maxn];
	matrix() { memset(g, 0, sizeof(g)); }
	void clr() { memset(g, 0, sizeof(g)); return ; }
	void init() { for (int i = 0; i < x; ++i) g[i][i] = 1; return ; }
	matrix operator * (const matrix& p) const {
		matrix z;
		for (int i = 0; i < x; ++i)
			for (int k = 0; k < x; ++k)
				for (int j = 0; j < x; ++j)
					add(z.g[i][j], (i64)g[i][k] * p.g[k][j] % mod);
		return z;
	}
} F, G;

matrix power(matrix x, int y) {
	matrix ans; ans.init();
	for (; y; y >>= 1) {
		if (y & 1) ans = ans * x;
		x = x * x;
	}
	return ans;
}

void work() {
	scanf("%d %d %d", &n, &x, &k);
	int ans = (i64)(x + k) * power(2 * k + 1, n - 1) % mod;
	F.clr(); G.clr();
	for (int i = 0; i < x; ++i)
		F.g[0][i] = 1;
	for (int i = 0; i < x; ++i)
		for (int j = 0; j < x; ++j)
			if (abs(i - j) <= k) G.g[i][j] = 1;
	F = F * power(G, n - 1);
	for (int i = 0; i < x; ++i)
		sub(ans, F.g[0][i]);
	printf("%d\n", ans);
	return ;
}

int main() {
	int T; scanf("%d", &T);
	while (T--) work();
	return 0;
}