传送门

文章目录

• 题意：
• 思路：

题意：

给你一个数组$a_i$，定义一个数组是好的当且仅当对于所有$i$都有$a_i!=i$。定义$f(a)$表示数组$a$中$i<j,a_i+a_j=i+j$的$(i,j)$对数。定义一个数组是极好的包含以下三个条件：
$(1)a$数组是好的。
$(2)l\le a_i\le r$
$(3)f(a)$在所有的好的数组中是最大的。
给定$l,r$，让你求出来有多少个极好的数组。
$n\le 2e5,-10^9\le l\le 1,n\le r\le 10^9$

思路：

首先考虑$f(a)$最大的时候是什么情况，如果没有$a_i!=i$的条件，肯定是$a_i=i$的时候最大。现在有这个条件，那么我们可以将其加上一个偏移量$k$，即$a_i+k,a_i-k$，考虑长度$n$的数组，一定是一半$a_i+k$，另一半$a_i-k$，这样$f(a)=\lceil \frac{n}{2}\rceil \ast \lfloor \frac{n}{2}\rfloor$，此时一定是最大的。
通过以上分析，我们知道每个位置一定是加上或减去一个偏移量$k$构造出来的数组才有可能是极好的数组，由于$a_i$的范围有限制，我们分以下几种情况讨论：
$(1)k\le min(1-l,r-n)$
此时对于每个位置$a_i+k,a_i-k$两个数都不会超过范围，所以当$n$为偶数的时候，可以选择$n/2$个位置$+k$，贡献就是$C(n,n/2)$，是奇数的时候，可以选择$n/2$个位置$+k$或者$n/2+1$个位置$+k$。
$(2)k>min(1-l,r-n)$
我们设$k=min(1-l,r-n)+1$，那么有$max(1,l+k)-1$个人必须$+k$，有$n-min(n,r-k)$个人必须$-k$，否则他们就越界了。设减去上述两个剩下的位置是$rest$，那么问题转换成跟第一种情况一样了，只是从$n$变成了$rest$。
注意第二种情况我们不需要特判，只需要在求$C(n,m)$的时候判断一下$n,m<0,n<m$的情况直接返回$0$即可。
第二种情况最多迭代$n$次，复杂度$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; } /**/

总结

以上是生活随笔为你收集整理的Educational Codeforces Round 111 (Rated for Div. 2) D. Excellent Arrays 组合数学的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。