D - Excellent Arrays
我们定义一个长度为 \(n\) 的整数序列 \(a\) 是好的仅当对于任意整数 \(i\in[1,n]\) ，都有 \(a_i\not=i\) 。
设 \(F(a)\) 等于满足 \(1\leq i<j\leq n,a_i+a_j=i+j\) 的 \((i,j)\) 对数。
我们定义一个长度为 \(n\) 的序列 \(a\) 是极好的，仅当：
- \(a\) 是好的。
- 对于任意整数 \(i\in[1,n]\) ，\(l\leq a_i\leq r\) 。
- \(F(a)\) 的值是所有好的、长度为 \(n\) 的序列中最大的。
给定 \(n,l,r\) ，求极好的序列个数对 \(10^9+7\) 取模后的结果。\(T\) 组数据。
\(1\leq t\leq 10^3,\ 2\leq n\leq 2\cdot10^5,\ \sum n\leq 2\cdot 10^5,\ -10^9\leq l\leq 1,n\leq r\leq 10^9\)
最关键的点是设 \(a_i=i+b_i\) .
那么 \(i+b_i+j+b_j=i+j\) ，即 \(b_i=-b_j\) 且 \(b_i\not=0\) .
所以，\(b\) 中所有值取两种最好，即 \(+x\) 和 \(-x\) \((x>0)\)，一种个数为 \(\lfloor\frac{n}{2}\rfloor\) ，一种个数为 \(n-\lfloor\frac{n}{2}\rfloor\) ，记为 \(A\) 和 \(B\) .
考虑枚举 \(x\) ，每个数，有三种情况，只能 \(+x\) ，只能 \(-x\) ，既可以 \(+x\) 也可以 \(-x\) .
只需要统计每种情况的个数，设为 \(cnt_1\) ，\(cnt_2\) , \(cnt_3\) ，
如果 \(A=B\) ，方案数为 \(\dbinom{cnt_3}{A-cnt_1}\) .
如果 \(A\not= B\) ，方案数为 \(\dbinom{cnt_3}{A-cnt_1}+\dbinom{cnt_3}{A-cnt_2}\) .
但是，这个 \(x\) 的范围可以达到 \(10^9\) . 这就无法循环 .
不过，很多 \(x\) 的情况是相同的 ，这些情况都是 \(cnt_3=n\) .
来考虑 \(cnt_3=n\) 的 \(x\) 的范围，考虑极值的情况，对于左端点是 \(\min(l-1,r-1)\) , 右端点的情况是 \(\min(r-n,n-1)\) ，因此，范围就是 \(x\in[1,\min(\min(l-1,r-1),\min(r-n,n-1))]\) .
在这个范围内，\(cnt_3=n\) ，对于每个 \(x\in[1,\min(\min(l-1,r-1),\min(r-n,n-1))]\) ，
如果 \(A=B\) ，方案数为 \(\dbinom{n}{A}\) .
如果 \(A\not=B\) ，方案数为 \(\dbinom{n}{A}+\dbinom{n}{B}\) .
剩下的 \(x\) 的取值范围大小不超过 \(n\) .
如果 \(x\) 增加，至少会导致一个数不能 \(+x/-x\) ，在 \(n\) 次操作后，必定只能 \(+x/-x\) 的数其中有一种超过 \(\min(A,B)\) .
所以，可以记录每个数只能 \(+x/-x\) 的 \(x\) 值 ，用 map 或 哈希表存储 .
每次，可以 \(O(1)\) 或 \(O(\log n)\) 地求出当前的 \(cnt_1\) 和 \(cnt_2\) .
用上面那个式子计算贡献即可 .
时间复杂度 : \(\mathrm O(tn)\)
空间复杂度 : \(\mathrm O(n)\)
code
#include<bits/stdc++.h>
using namespace std;
inline int read(){
char ch=getchar();
while((ch<'0'||ch>'9')&&(ch!='-'))ch=getchar();
bool f=false;
if(ch=='-'){
f=true;
ch=getchar();
}
int res=0;
while(ch>='0'&&ch<='9'){
res=(res<<3)+(res<<1)+ch-'0';
ch=getchar();
}
if(f)res=-res;
return res;
}
inline void print(int res){
if(res==0){
putchar('0');
return;
}
int a[10],len=0;
while(res>0){
a[len++]=res%10;
res/=10;
}
for(int i=len-1;i>=0;i--)
putchar(a[i]+'0');
}
const int mod=1e9+7;
int t;
int n,l,r;
int p[200010],inv[200010];
unordered_map<int,int>cnt1,cnt2;
inline int ksm(int x,int k){
if(k==0)return 1;
int res=ksm(x,k>>1);
res=1ll*res*res%mod;
if(k&1)res=1ll*res*x%mod;
return res;
}
inline int C(int a,int b){
return 1ll*p[a]*inv[b]%mod*inv[a-b]%mod;
}
void solve(){
cnt1.clear();cnt2.clear();
n=read();l=read();r=read();
int mx=r;
for(int i=1;i<=n;i++){
cnt1[i-l+1]++;
cnt2[r-i+1]++;
mx=max(i-l+1,r-i+1);
}
int a=n/2,b=n-a,sum1=0,sum2=0;
int mn=min(min(1-l,r-1),min(r-n,n-l));
int ans=1ll*mn*C(n,a)%mod;
for(int i=mn+1;i<mx;i++){
if(cnt1.find(i)!=cnt1.end())sum1++;
if(cnt2.find(i)!=cnt2.end())sum2++;
if(sum1>a||sum2>b)break;
int tmp=1ll*C(n-sum1-sum2,a-sum1);
ans=(ans+tmp)%mod;
}
if(a!=b){
sum1=0;sum2=0;
ans=(ans+1ll*mn*C(n,b)%mod)%mod;
for(int i=mn+1;i<mx;i++){
if(cnt1.find(i)!=cnt1.end())sum1++;
if(cnt2.find(i)!=cnt2.end())sum2++;
if(sum1>b||sum2>a)break;
int tmp=1ll*C(n-sum1-sum2,a-sum2);
ans=(ans+tmp)%mod;
}
}
print(ans);
putchar('\n');
}
int main(){
p[0]=1;
for(int i=1;i<200010;i++)p[i]=1ll*p[i-1]*i%mod;
for(int i=0;i<200010;i++)inv[i]=ksm(p[i],mod-2);
t=read();
while(t--){
solve();
}
return 0;
}
/*inline? ll or int? size? min max?*/r4eerrree3ee
E - Stringforce
设 \(s\) 是一个由前 \(k\) 个小写字母构成的字符串，\(v\) 是前 \(k\) 个小写字母中的某一个。定义 \(\mathrm{MaxLen}(s,v)\) 表示 \(s\) 所有仅由字母 \(v\) 构成的连续子串的最长长度。
定义 \(s\) 的价值为所有 \(\mathrm{MaxLen}(S,v)\) 的最小值，其中 \(v\) 取遍前 \(k\) 个小写字母。
现在给定一个长度为 \(n\) 的字符串 \(s\)，\(s\) 中字母要么是前 \(k\) 个小写字母中的某一个，要么是问号。你需要将 \(s\) 中的每一个问号替换成前 \(k\) 个小写字母中的一个，并最大化 \(s\) 的价值。方便起见，你只需要输出这个最大的价值即可。
\(1\leq n\leq 2\cdot 10^5,1\leq k\leq 17\)
看到为所有 \(\mathrm {MaxLen}(S,v)\) 的最小值，输出这个最大值，想到要二分答案 .
现在的问题就是如何判断，二分答案 \(x\) .
因为这个 \(k\) 非常的小，想到一个最原始的状压 \(dp\) ，\(f(i,s)\) 表示到了第 \(i\) 位，是否能满足 \(s\) 中的集合 \(\mathrm {Maxlen}(s,v)\geq k\) . 发现这个 \(dp\) 是 \(\mathrm O(n2^k)\) 的，非常不好 .
换一种表达方式，\(f(s)\) 表示，满足 \(s\) 中集合 \(\mathrm{Maxlen}(s,v)\geq k\) 最少需要的前缀 .
每次预处理 \(len(i,j)\) 表示第 \(i\) 个字符，从第 \(j\) 位往后最少需要多少位使得连续字符的长度至少为 \(k\) .
对于当前状态 \(f(s)\) ，枚举新加入的一个字符 \(i\)，
\(f(s|2^i)=\min(f(s|2^i),len(i,f(s)))\) .
预处理是 \(\mathrm O(kn)\) 的，\(dp\) 是 \(\mathrm O(k2^k)\) 的，加上二分的 \(\log\) .
时间复杂度 : \(\mathrm O((kn+k2^k)\log n)\)
空间复杂度 : \(O(kn+k2^k)\)
code
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9+10;
int n,k;
string s;
int a[200010][18],b[200010][18];
int f[1<<18];
bool check(int len){
for(int i=0;i<=n;i++)for(int j=0;j<k;j++)b[i][j]=n;
for(int j=0;j<k;j++){
for(int i=n-1;i>=0;i--){
b[i][j]=min(b[i][j],b[i+1][j]);
if(a[i][j]>=len)b[i][j]=min(b[i][j],i+len-1);
}
}
for(int mask=0;mask<(1<<k);mask++)f[mask]=inf;
f[0]=0;
for(int mask=0;mask<(1<<k);mask++){
if(f[mask]==inf)continue;
for(int i=0;i<k;i++){
if(((mask&(1<<i))>0)||(b[f[mask]][i]>=n))continue;
f[mask|(1<<i)]=min(f[mask|(1<<i)],b[f[mask]][i]+1);
}
}
return f[(1<<k)-1]<=n;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>k>>s;
for(int c=0;c<k;c++){
int j=-1;
for(int i=0;i<n;i++){
j=max(j,i-1);
while(j+1<n&&(s[j+1]=='?'||s[j+1]==c+'a'))j++;
if(j>=i)a[i][c]=j-i+1;
}
}
int low=0,high=n+1,ans=0;
while(low<high){
int mid=(low+high)>>1;
if(check(mid)){
ans=max(ans,mid);
low=mid+1;
}
else{
high=mid;
}
}
cout<<ans<<endl;
return 0;
}
/*inline? ll or int? size? min max?*/
F - Jumping Around
有一条坐标轴，上面有 \(n\) 个石头，第 \(i\) 个石头在 \(a_i\) 位置. 每个石头的位置唯一，满足 \(a_1<a_2<\cdots <a_n\) .
有一个机械青蛙在第 \(s\) 个石头上，有一个跳跃半径 \(d\) ，有一个跳跃距离 \(k\) ，青蛙可以跳到距离在 \([d-k,d+k]\) 之内任意方向的石头.
有 \(q\) 组询问，每个询问形如 \(i,k\) ，表示询问是否可以在跳跃距离为 \(k\) 的情况下从第 \(s\) 个石头跳到第 \(i\) 个石头.
\(1\leq n,q\leq 2\cdot 10^5,1\leq s\leq n,1\leq d\leq 10^6,1\leq a_i\leq 10^6,\ a_1<a_2<\cdots <a_n,1\leq i\leq n,1\leq k\leq 10^6\)
发现对于特定的 \(i\) ，\(k\) 具有单调性，可以考虑求出最小的 \(k\) 使得 \(s,i\) 之间可以互相到达.
对于 \(i,j\) 之间，存在一条 \(|a_i-d-a_j|\) 的边和一条 \(|a_i+d-a_j|\) 的边.
那么，就是在一个 \(n\) 个点，\(n^2\) 条边的图上求 \(s\) 到 \(i\) 的最小瓶颈路径，从 \(s\) 到 \(i\) 的所有最小瓶颈路径都在该图的最小生成树上. 那么，就是要求该图的最小生成树.
边的数量非常大，达到了 \(n^2\) 级别，就不能考虑用 kruscal 做了，要用 prim .
如何计算已经在树上的点和非树点的最小连边.
首先 ，在最小生成树上的点都可以跳到位置 \(a_i-d\) 和位置 \(a_i+d\) ，那么，加入在离 \(a_i-d\) 和 \(a_i+d\) 的，且不在树上的点最优. 可以用两个 set 维护，一个 set \(S_2\) 保存每个在树上的点的 \(a_i-d\) 和 \(a_i+d\) 位置和编号；另一个 set \(S_1\) 维护每个在非树的点和树上的点的最小距离 \(dis(i)\)，编号 \(i_1\) 和所连树点的编号 \(i_2\) .
考虑有几种操作，
- 在 \(S_1\) 中删除 \(i\) ，找到左边，右边分别距离 \(i\) 最近的两个非树点 \(x,y\) ，找到距离 \(x\) 最近的右侧树点，跟新 \(dis(x),S_1\) ；找到距离 \(y\) 最近的左侧树点，跟新 \(dis(x),S_1\) . 这是 erase 操作.
- 在 \(S_2\) 中加入点 \(i\) ，有两个位置 \(a_i-d,a_i+d\) ，是等价的. 找到 \(p\) 左边和右边最近的点 \(x,y\) ，跟新 \(dis(x),S_1\) ，\(dis(y),S_2\) . 这是 insert 操作.
首先是查询 \(S_1\) 中最小的元素 \(dis(i),i_1,i_2\)，现在 \(S_2\) 中直接插入 \(a_{i_1}-d,i_1\) 和 \(a_{i_1}+d,i_1\) ，再对 \(i_1\) 进行删除操作（顺序不能反），对 \(a_{i_1}-d\) 和 \(a_{i_1}+d\) 进行 insert 操作 .
此时，可以在 \(O(nlogn)\) 时间内建出一棵最小生成树.
之后只需要在最小生成树上求一个简单的 \(dp\) ，用 \(dp(i)\) 表示从根节点 \(s\) 到节点 \(i\) 路径上的边权最大值.
之后询问的时候就可以 \(O(1)\) 地查询 .
时间复杂度 : \(O(nlogn+q)\)
空间复杂度 : \(O(nlogn)\) ? set的内存怎么算
code
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
int n,q,s,d;
int a[200010];
int dis[200010];
set<pair<int,int> >s1,s2; //pos i
bool ok[200010];
priority_queue<pair<int,pair<int,int> > >Q; //dis u v
void ins(int pos,int id){
set<pair<int,int> >::iterator itr=s1.lower_bound(make_pair(pos,-1));
set<pair<int,int> >::iterator itl=s1.upper_bound(make_pair(pos,inf));
if(itl!=s1.begin()){
itl--;
int np=itl->first,nid=itl->second;
if(abs(np-pos)<dis[nid]){
dis[nid]=abs(np-pos);
Q.push(make_pair(-dis[nid],make_pair(nid,id)));
}
}
if(itr!=s1.end()){
int np=itr->first,nid=itr->second;
if(abs(np-pos)<dis[nid]){
dis[nid]=abs(np-pos);
Q.push(make_pair(-dis[nid],make_pair(nid,id)));
}
}
}
void era(int u){
s1.erase(make_pair(a[u],u));
set<pair<int,int> >::iterator itr=s1.lower_bound(make_pair(a[u],-1));
set<pair<int,int> >::iterator itl=s1.upper_bound(make_pair(a[u],inf));
if(itl!=s1.begin()){
itl--;
int id=itl->second; // dot : id pos : a[id] find right
set<pair<int,int> >::iterator it=s2.lower_bound(make_pair(a[id],-1));
if(it!=s2.end()){
int id2=it->second;
if(abs(it->first-a[id])<dis[id]){
dis[id]=abs(it->first-a[id]);
Q.push(make_pair(-dis[id],make_pair(id,id2)));
}
}
}
if(itr!=s1.end()){
int id=itr->second;
set<pair<int,int> >::iterator it=s2.upper_bound(make_pair(a[id],inf));
if(it!=s2.begin()){
it--;
int id2=it->second;
if(abs(a[id]-it->first)<dis[id]){
dis[id]=abs(a[id]-it->first);
Q.push(make_pair(-dis[id],make_pair(id,id2)));
}
}
}
}
vector<pair<int,int> >g[200010];
inline void add_edge(int u,int v,int cost){
g[u].push_back(make_pair(v,cost));
g[v].push_back(make_pair(u,cost));
}
int dp[200010];
void dfs(int x,int fa){
for(int i=0;i<(int)g[x].size();i++){
int to=g[x][i].first,cost=g[x][i].second;
if(to==fa)continue;
dp[to]=max(dp[to],max(dp[x],cost));
dfs(to,x);
}
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>q>>s>>d;
s--;
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<n;i++)if(i!=s)s1.insert(make_pair(a[i],i));
for(int i=0;i<n;i++)dis[i]=inf;
s2.insert(make_pair(a[s]-d,s));
s2.insert(make_pair(a[s]+d,s));
ins(a[s]-d,s);
ins(a[s]+d,s);
ok[s]=true;
while(!Q.empty()){
int dis=-Q.top().first,u=Q.top().second.first,v=Q.top().second.second;
Q.pop();
if(ok[u])continue;
ok[u]=true;
add_edge(u,v,dis);
s2.insert(make_pair(a[u]-d,u));
s2.insert(make_pair(a[u]+d,u));
era(u);
ins(a[u]-d,u);
ins(a[u]+d,u);
}
dfs(s,-1);
for(int i=0;i<q;i++){
int x,k;
cin>>x>>k;
x--;
if(dp[x]>k)cout<<"No\n";
else cout<<"Yes\n";
}
return 0;
}