Fancy Arrays
洋洋强到爆炸啊。
根据某个差分数组可以得出最小值的位置(即使有多个也会因为差分数组有区别而对应不同原序列),所以钦定最小值后可以得出所有 \(a_i\geq0\) 的方案数,不难得出区间为 [0,x+k],并且最小的大于 x 的数一定合法。
然后减去所有值都在 [0,x) 的方案即可。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<bitset>
using namespace std;
#define db double
#define ll long long
#define ull unsigned long long
#define ld long double
#define b1t bitset
const int MAXN=45;
const int Mod=1e9+7;
const int INF=0x3f3f3f3f;
void read(int &x){
x=0;int f=1;char s=getchar();
while(s<'0'||s>'9'){
if(s=='-') f=-1;s=getchar();
}
while(s>='0'&&s<='9'){
x=(x<<3)+(x<<1)+(s^48);s=getchar();
}
x*=f;
}
int T,n,m,x;
ll ksm(ll a,int b){
ll res=1;
while(b){
if(b&1) res=res*a%Mod;a=a*a%Mod;b>>=1;
}return res;
}
struct mat{
ll f[MAXN][MAXN];
void clear(){
for(int i=0;i<x;i++){
for(int j=0;j<x;j++){
f[i][j]=0;
}
}
}
void init(){
for(int i=0;i<x;i++) f[i][i]=1;
}
}a;
mat operator*(mat a,mat b){
mat c;c.clear();
for(int k=0;k<x;k++){
for(int i=0;i<x;i++){
for(int j=0;j<x;j++){
c.f[i][j]=(c.f[i][j]+a.f[i][k]*b.f[k][j]%Mod)%Mod;
}
}
}
return c;
}
int main(){
read(T);
while(T--){
read(n);read(x);read(m);
ll sum=1ll*(x+m)*ksm((m<<1)+1,n-1)%Mod;
if(n==1){
printf("%lld\n",m);continue;
}
a.clear();
for(int i=0;i<x;i++){
for(int j=0;j<x;j++){
if(abs(i-j)<=m) a.f[i][j]=1;
}
}
mat tmp;tmp.clear();
for(int i=0;i<x;i++) tmp.f[0][i]=1;
int oo=n-1;
while(oo){
if(oo&1) tmp=tmp*a;a=a*a;oo>>=1;
}
for(int i=0;i<x;i++) sum=(((sum-tmp.f[0][i])%Mod)+Mod)%Mod;
printf("%lld\n",sum);
}
return 0;
}