2024/4/8 课件补题
[AGC055B] ABC Supremacy
思维题。
发现所有的 \(ABC\)，\(BCA\)，\(CAB\) 都可以任意向左向右移动，所以只需要把所有的 \(ABC\) 挪到字符串结尾即可，具体操作时可以删掉再比对 \(s\) 和 \(t\) 是否相同。
#include <bits/stdc++.h>
using namespace std;
#define ld long double
template <typename T>
inline T read(){
T x=0;char ch=getchar();bool fl=false;
while(!isdigit(ch)){if(ch=='-')fl=true;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return fl?-x:x;
}
#define read() read<int>()
const int maxn = 5e5 + 10;
int n;
string s,t;
int main(){
cin>>n;
cin>>s>>t;
string S="",T="";
for(int i=0;i<n;i++){
S+=s[i];
if(S.size()>=3){
string tmp="@@@";
tmp[0]=S[S.size()-3];
tmp[1]=S[S.size()-2];
tmp[2]=S[S.size()-1];
if(tmp=="ABC" || tmp=="BCA" || tmp=="CAB"){
S.pop_back();
S.pop_back();
S.pop_back();
}
}
T+=t[i];
if(T.size()>=3){
string tmp="@@@";
tmp[0]=T[T.size()-3];
tmp[1]=T[T.size()-2];
tmp[2]=T[T.size()-1];
if(tmp=="ABC" || tmp=="BCA" || tmp=="CAB"){
T.pop_back();
T.pop_back();
T.pop_back();
}
}
}
if(S==T)puts("YES");
else puts("NO");
return 0;
}
PERIODNI - Periodni
关键是建出小根的笛卡尔树，每个节点所在的子树管辖的高度范围为 \((h_{fa_i},h_i]\)，这样 \(dp\) 可以做到不重不漏还好计算。
令 \(tmp_i\) 为当前节点孩子子树一共放了 \(i\) 个的方案数，则递推公式为：
\[f[u][i]=\sum_{j=0}^{i}tmp_{i-j}\binom{H}{j}\binom{W-(i-j)}{j}\times j\ ! \]#include <bits/stdc++.h>
using namespace std;
#define ld long double
template <typename T>
inline T read(){
T x=0;char ch=getchar();bool fl=false;
while(!isdigit(ch)){if(ch=='-')fl=true;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return fl?-x:x;
}
#define read() read<int>()
const int maxn = 1e6 + 10;
const int maxm = 1e3 + 10;
const int P = 1e9 + 7;
inline void add(int &x,int y){
x+=y;
if(x>=P)x-=P;
}
inline int power(int a,int b){
int res=1;
while(b){
if(b&1)res=1LL*a*res%P;
a=1LL*a*a%P;
b>>=1;
}
return res;
}
int head[maxn],cnt;
struct edge{
int to,nxt;
}e[maxn];
inline void link(int u,int v){
e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;
}
int n,k,h[maxn],fac[maxn],invfac[maxn],stk[maxn],top;
int tmp[maxm],f[maxm][maxm];
int ls[maxn],rs[maxn],fa[maxn],sz[maxn];
inline void init(){
fac[0]=1;
for(int i=1;i<=1000000;i++)fac[i]=1LL*fac[i-1]*i%P;
invfac[1000000]=power(fac[1000000],P-2);
for(int i=1000000;i>=1;i--)invfac[i-1]=1LL*invfac[i]*i%P;
}
inline int C(int n,int m){
if(n<m || n<0 || m<0)return 0;
return 1LL*fac[n]*invfac[n-m]%P*invfac[m]%P;
}
void dfs(int u){
sz[u]=1;
if(ls[u])dfs(ls[u]);
if(rs[u])dfs(rs[u]);
sz[u]+=sz[ls[u]]+sz[rs[u]];
for(int i=0;i<=k;i++)tmp[i]=0;
for(int i=1;i<=min(sz[u],k);i++){
for(int j=0;j<=i;j++)add(tmp[i],1LL*f[ls[u]][j]*f[rs[u]][i-j]%P);
}
tmp[0]=1;
for(int i=0;i<=min(sz[u],k);i++){
for(int j=0;j<=i;j++){
int H=h[u]-h[fa[u]],W=sz[u];
int res=1LL*tmp[i-j]*C(H,j)%P*C(W-(i-j),j)%P*fac[j]%P;
add(f[u][i],res);
}
}
}
int main(){
init();
n=read();k=read();
for(int i=1;i<=n;i++)h[i]=read();
for(int i=1;i<=n;i++){
while(top && h[i]<h[stk[top]])ls[i]=stk[top--];
if(top)rs[stk[top]]=i;
stk[++top]=i;
}
for(int i=1;i<=n;i++){
if(ls[i])fa[ls[i]]=i;
if(rs[i])fa[rs[i]]=i;
}
for(int i=1;i<=n;i++)if(fa[i])link(fa[i],i);
int rt=stk[1];
f[0][0]=1;
dfs(rt);
cout<<f[rt][k]<<endl;
return 0;
}