分析
对于excellent的 \(a\) 来说 \(|a_i-i|=x\) 的值是固定的,考虑枚举它
一半正一半负时函数值是最大的,当 \(n\) 为奇数时要分为两种情况(不过可以通过杨辉三角合并)
问题是,由于 \(l,r\) 的范围,并不能做到所有位置都能可正可负,不过不超过 \(mn=\min\{1-l,r-n\}\) 时是可以的,也就是 \(C(n,mid)*mn\)。
之后应分为两个阶段,绝对值增加1会产生1个不能可正可负,不超过 \(mx=\max\{1-l,r-n\}\) 时,枚举 \(i(mn+i=x)\) 即为 \(C(n-i,mid-i)\)
或者产生2个不能可正可负,此时在上一阶段的上界基础上继续增加,就是 \(C(n-i*2-(mx-mn),mid-i-(mx-mn))\)
注意 \(i\) 在第一阶段超过 \(mid\) 抑或是第二阶段超过 \(mid-(mx-mn)\) 时已经无法产生贡献,此时可直接终止,那么复杂度就是 \(O(n)\) 的
代码(里面的 \(mx\) 已经减去了 \(mn\))
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int N=200011,mod=1000000007;
int inv[N],fac[N],n,L,R,mn,mx,mid,odd,ans;
int iut(){
int ans=0,f=1; char c=getchar();
while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();
while (isdigit(c)) ans=ans*10+c-48,c=getchar();
return ans*f;
}
void print(int ans){
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
void Mo(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
int C(int n,int m){return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;}
int main(){
fac[0]=inv[0]=fac[1]=inv[1]=1;
for (int i=2;i<N;++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for (int i=2;i<N;++i) fac[i]=1ll*fac[i-1]*i%mod,inv[i]=1ll*inv[i-1]*inv[i]%mod;
for (int T=iut();T;--T,putchar(10)){
n=iut(),L=iut(),R=iut(),mid=(n+1)>>1;
mn=min(1-L,R-n),mx=max(1-L,R-n)-mn;
odd=n&1,ans=1ll*mn*C(n+odd,mid)%mod;
for (int i=1;i<=mx&&i<=mid;++i) Mo(ans,C(n-i+odd,mid-i));
for (int i=1;i<=mid-mx&&i*2+mx<=n;++i) Mo(ans,C(n-i*2-mx+odd,mid-mx-i));
print(ans);
}
return 0;
}
标签:Arrays,mn,mid,int,CF1550D,ans,Excellent,mx,mod
From: https://www.cnblogs.com/Spare-No-Effort/p/18010545