题目
称一个长为n的数列a是fancy的，当且仅当：
1. 数组内至少有一个元素在[x,x+k-1]之间
2. 相邻项的差的绝对值不超过k，即
t(t<=50)组样例，每次给定n(1<=n<=1e9),x(1<=x<=40),
求fancy的数组的数量，答案对1e9+7取模
思路来源
灵茶山艾府群 && 官方题解
题解
看到至少的字眼，首先想到容斥，用总的减不满足的，
本题中，合法方案数=[最小值<=x+k-1的方案数]-[最大值<x的方案数]
最小值<=x+k-1的方案数
第一个数字选0，后面每个数都有2k+1种选择方式，最后把最小值往上平移到[0,x+k-1]之间
方案数为
最小值<x的方案数
即长为n的数列，使用的值均在[0,x-1]的方案数，
注意到x<=40，所以可以dp[i][j]表示长为i的数组最后一个是j的方案数
转移时，只要abs(j1-j2)<=k，就可以从j1转移到j2，
构造上述转移矩阵，矩阵快速幂求出其n-1次幂，文章来源：https://www.toymoban.com/news/detail-745067.html
由于长度为1时对应的[0,x-1]的向量均为1，所以将每一行的和从答案中减掉即可文章来源地址https://www.toymoban.com/news/detail-745067.html
代码
// Problem: F. Fancy Arrays
// Contest: Codeforces - Educational Codeforces Round 157 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1895/problem/F
// Memory Limit: 512 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int mod=1e9+7;
int t,n,x,k;
int modpow(int x,int n,int mod){
int res=1;
for(;n;n>>=1,x=1ll*x*x%mod){
if(n&1)res=1ll*res*x%mod;
}
return res;
}
struct mat{
static const int N=42;
ll c[N][N];
int m,n;
mat(){
memset(c,0,sizeof(c));
m=n=N;
}
mat(int a,int b):m(a),n(b){
memset(c,0,sizeof(c));
}
void clear(){
memset(c,0,sizeof(c));
}
void E(){
int mn=min(m,n);
for(int i=0;i<mn;i++){
c[i][i]=1;
}
}
mat operator *(const mat& x){
mat ans(m,x.n);
for(int i=0;i<m;i++)
for (int k=0;k<n;k++)
{
if(!c[i][k])continue;//小剪枝
for (int j=0;j<x.n;j++)
(ans.c[i][j]+=c[i][k]*x.c[k][j]%mod)%=mod;//能不取模 尽量不取模
}
//这里maxn=2 故不会超过ll 视具体情况 改变内部取模情况
return ans;
}
friend mat operator^(mat x,ll n){//幂次一般为ll 调用时a=a^(b,n) 等价于a=b^n
mat ans(x.m, x.m);
ans.E();
for(;n;n>>=1,x=x*x){//x自乘部分可以预处理倍增，也可以用分块加速递推
if(n&1)ans=ans*x;
}
return ans;
}
};
int sol(){
sci(n),sci(x),sci(k);
int ans=1ll*(x+k)*modpow(2*k+1,n-1,mod)%mod;
if(!x)return ans;
mat a(x,x);
rep(i,0,x-1){
rep(j,0,x-1){
if(abs(i-j)<=k)a.c[i][j]=1;
}
}
a=a^(n-1);
rep(i,0,x-1){
int sum=0;
rep(j,0,x-1){
sum=(sum+a.c[i][j])%mod;
}
ans=(ans-sum+mod)%mod;
}
return ans;
}
int main(){
sci(t); // t=1
while(t--){
pte(sol());
}
return 0;
}到了这里，关于Educational Codeforces Round 157 (Rated for Div. 2) F. Fancy Arrays(容斥+组合数学)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
