題目

稱一個(gè)長為n的數(shù)列a是fancy的，當(dāng)且僅當(dāng)：

1. 數(shù)組內(nèi)至少有一個(gè)元素在[x,x+k-1]之間

2. 相鄰項(xiàng)的差的絕對(duì)值不超過k，即

t(t<=50)組樣例，每次給定n(1<=n<=1e9),x(1<=x<=40),

求fancy的數(shù)組的數(shù)量，答案對(duì)1e9+7取模

思路來源

靈茶山艾府群 && 官方題解

題解

看到至少的字眼，首先想到容斥，用總的減不滿足的，

本題中，合法方案數(shù)=[最小值<=x+k-1的方案數(shù)]-[最大值<x的方案數(shù)]

最小值<=x+k-1的方案數(shù)

第一個(gè)數(shù)字選0，后面每個(gè)數(shù)都有2k+1種選擇方式，最后把最小值往上平移到[0,x+k-1]之間

方案數(shù)為

最小值<x的方案數(shù)

即長為n的數(shù)列，使用的值均在[0,x-1]的方案數(shù)，

注意到x<=40，所以可以dp[i][j]表示長為i的數(shù)組最后一個(gè)是j的方案數(shù)

轉(zhuǎn)移時(shí)，只要abs(j1-j2)<=k，就可以從j1轉(zhuǎn)移到j(luò)2，

構(gòu)造上述轉(zhuǎn)移矩陣，矩陣快速冪求出其n-1次冪，

由于長度為1時(shí)對(duì)應(yīng)的[0,x-1]的向量均為1，所以將每一行的和從答案中減掉即可文章來源地址http://www.zghlxwxcb.cn/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 故不會(huì)超過ll 視具體情況 改變內(nèi)部取模情況
        return ans;
    }
    friend mat operator^(mat x,ll n){//冪次一般為ll 調(diào)用時(shí)a=a^(b,n) 等價(jià)于a=b^n
        mat ans(x.m, x.m);
    	ans.E();
        for(;n;n>>=1,x=x*x){//x自乘部分可以預(yù)處理倍增，也可以用分塊加速遞推
            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;
}

到了這里，關(guān)于Educational Codeforces Round 157 (Rated for Div. 2) F. Fancy Arrays(容斥+組合數(shù)學(xué))的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！