数据结构
【CF380C】 Sereja and Brackets
题目描述
- 本题中「合法括号串」的定义如下：
- 空串是「合法括号串」。
- 若 \(s\) 是「合法括号串」，则 \((s)\) 是「合法括号串」。
- 若 \(s,t\) 是「合法括号串」，则 \(st\) 是「合法括号串」。
- 有一个括号串 \(s\)。\(m\) 次操作。操作有一种：
l r：求字符串 \(t=s_ls_{l+1}\cdots s_r\) 的所有 子序列 中，长度最长的「合法括号串」，输出长度即可。
- \(1\le |s|\le 10^6\)，\(1\le m\le 10^5\)。
解题思路
首先，将 \((,)\) 转化成 \(+1,-1\) ，就是找一个子序列，使得所有的前缀和 \(\ge 0\) ，最后一个前缀和为 \(0\) 。
我们考虑使用线段树，维护没能匹配的 \((\) 数量与没能匹配的 \()\) 数量。
每次两个区间合并时，就是将两区间没匹配的 \(()\) 个配对了进行计算即可。
由于我们默认没匹配的 \((\) 尽量靠前，没匹配的 \()\) 尽量靠后，不会出现匹配不了的问题。
时间复杂度 \(O(nlogn)\) 。
Code
#include<bits/stdc++.h>
using namespace std;
struct datay
{
int v1,v2;
}f[4000005];
string a;
int n,m;
void build(int x,int l,int r)
{
if(l==r)
{
if(a[l]=='(')f[x].v1=1,f[x].v2=0;
else f[x].v1=0,f[x].v2=1;
return;
}
int lc=(x<<1),rc=(x<<1)|1,mid=(l+r)>>1;
build(lc,l,mid),build(rc,mid+1,r);
f[x].v1=f[lc].v1+f[rc].v1-min(f[lc].v1,f[rc].v2);
f[x].v2=f[lc].v2+f[rc].v2-min(f[lc].v1,f[rc].v2);
return;
}
datay query(int x,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr)return f[x];
int mid=(l+r)>>1,lc=(x<<1),rc=(x<<1)|1;
if(qr<=mid)return query(lc,l,mid,ql,qr);
if(ql>mid)return query(rc,mid+1,r,ql,qr);
datay z,q=query(lc,l,mid,ql,qr),w=query(rc,mid+1,r,ql,qr);
z.v1=q.v1+w.v1-min(q.v1,w.v2);
z.v2=q.v2+w.v2-min(q.v1,w.v2);
return z;
}
int main()
{
int x,y;datay z;
cin>>a,n=a.size();
a=' '+a,build(1,1,n);
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y),z=query(1,1,n,x,y);
printf("%d\n",y-x+1-z.v1-z.v2);
}
return 0;
}
【梦熊】 对称之美
题目描述
给出 \(n,k\) \((1 \le n,k \le 10^{14})\) ，求 \(\sum_{i=0}^{k-1} C_{2i}^i n^i (mod\) \(k)\) 。
解题思路
首先，枚举可得，\(k=2\) 时答案为 \(1\) 。
\[C_{2n}^n=\frac{(2n)!}{n! \times n!} =2^n \times \frac{1 \times 3 \times ... \times (2n-1)}{n!} = (-2)^n \times \frac{\prod_{i=0}^{n-1}(k-1-2i)}{n!}=(-4)^n \times \frac{\prod_{i=0}^{n-1}(\frac{k-1}{2}-i)}{n!} \]带回原式并化简，即为：
\[\sum_{i=0}^{k-1} (-4n)^i \times C_{\frac{k-1}{2}}^{i}=(1-4n)^{\frac{k-1}{2}} \]结合二项式定理，由于 \(k\) 较大，需用龟速乘，结合快速幂 \(O(log^2n)\) 解决。
Code
#include<bits/stdc++.h>
using namespace std;
unsigned long long mod;
unsigned long long mul(unsigned long long x,unsigned long long y)
{
unsigned long long h=0;
while(y>0)
{
if(y&1)h=(h+x)%mod;
x=(x+x)%mod,y/=2;
}
return h;
}
unsigned long long poww(unsigned long long x,unsigned long long y)
{
x=(x+mod)%mod;
unsigned long long h=1;
while(y>0)
{
if(y&1)h=mul(h,x);
x=mul(x,x),y/=2;
}
return h;
}
void poi()
{
unsigned long long x,y;
cin>>x>>y;
if(x==1)
{
printf("1\n");
return;
}
mod=x;
cout<<(poww((4*mod+1-4*y)%mod,(mod-1)/2)+mod)%mod<<'\n';
return;
}
int main()
{
unsigned long long qwe;
cin>>qwe;
for(int i=1;i<=qwe;i++)poi();
return 0;
}