傳送門

文章目錄

• 題意：
• 思路：

題意：

給你一個數(shù)組$a_i$，定義一個數(shù)組是好的當(dāng)且僅當(dāng)對于所有$i$都有$a_i!=i$。定義$f(a)$表示數(shù)組$a$中$i<j,a_i+a_j=i+j$的$(i,j)$對數(shù)。定義一個數(shù)組是極好的包含以下三個條件：
$(1)a$數(shù)組是好的。
$(2)l\le a_i\le r$
$(3)f(a)$在所有的好的數(shù)組中是最大的。
給定$l,r$，讓你求出來有多少個極好的數(shù)組。
$n\le 2e5,?10^9\le l\le 1,n\le r\le 10^9$

思路：

首先考慮$f(a)$最大的時候是什么情況，如果沒有$a_i!=i$的條件，肯定是$a_i=i$的時候最大。現(xiàn)在有這個條件，那么我們可以將其加上一個偏移量$k$，即$a_i+k,a_i?k$，考慮長度$n$的數(shù)組，一定是一半$a_i+k$，另一半$a_i?k$，這樣$f(a)=?\frac{n}{2}???\frac{n}{2}?$，此時一定是最大的。
通過以上分析，我們知道每個位置一定是加上或減去一個偏移量$k$構(gòu)造出來的數(shù)組才有可能是極好的數(shù)組，由于$a_i$的范圍有限制，我們分以下幾種情況討論：
$(1)k\le min(1?l,r?n)$
此時對于每個位置$a_i+k,a_i?k$兩個數(shù)都不會超過范圍，所以當(dāng)$n$為偶數(shù)的時候，可以選擇$n/2$個位置$+k$，貢獻就是$C(n,n/2)$，是奇數(shù)的時候，可以選擇$n/2$個位置$+k$或者$n/2+1$個位置$+k$。
$(2)k>min(1?l,r?n)$
我們設(shè)$k=min(1?l,r?n)+1$，那么有$max(1,l+k)?1$個人必須$+k$，有$n?min(n,r?k)$個人必須$?k$，否則他們就越界了。設(shè)減去上述兩個剩下的位置是$rest$，那么問題轉(zhuǎn)換成跟第一種情況一樣了，只是從$n$變成了$rest$。
注意第二種情況我們不需要特判，只需要在求$C(n,m)$的時候判斷一下$n,m<0,n<m$的情況直接返回$0$即可。
第二種情況最多迭代$n$次，復(fù)雜度$O(n)$。

// Problem: D. Excellent Arrays // Contest: Codeforces - Educational Codeforces Round 111 (Rated for Div. 2) // URL: https://codeforces.com/contest/1550/problem/D // Memory Limit: 256 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") //#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #include<random> #include<cassert> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid ((tr[u].l+tr[u].r)>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n,l,r; LL fun[N],inv[N];LL qmi(LL a,LL b) {LL ans=1; a%=mod;while(b) {if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans%mod; }LL C(int a,int b) {if(a<0||b<0||a<b) return 0;return fun[a]*inv[b]%mod*inv[a-b]%mod; }int main() { // ios::sync_with_stdio(false); // cin.tie(0);fun[0]=1;for(int i=1;i<N;i++) fun[i]=fun[i-1]*i%mod;inv[N-1]=qmi(fun[N-1],mod-2);for(int i=N-2;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;int _; scanf("%d",&_);while(_--) {scanf("%d%d%d",&n,&l,&r);int begin=min(1-l,r-n);LL ans=0;if(n%2==0) ans+=C(n,n/2)*begin%mod;else ans+=(C(n,n/2)+C(n,n/2+1))%mod*begin%mod;for(LL t=begin+1,cnt=n;cnt;t++,cnt--) {int lcnt=max(1ll,l+t)-1;int rcnt=n-min(1ll*n,r-t);int rest=n-lcnt-rcnt;if(n%2==0) ans+=C(rest,n/2-lcnt),ans%=mod;else ans+=(C(rest,n/2-rcnt)+C(rest,n/2-rcnt+1))%mod,ans%=mod;}printf("%lld\n",ans%mod);}int c;return 0; } /**/

總結(jié)

以上是生活随笔為你收集整理的Educational Codeforces Round 111 (Rated for Div. 2) D. Excellent Arrays 组合数学的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。