前言
数论迎我归，数学送我葬
组合数学不容易，又有 DP 当
T3 刚爆零，T4 又遭殃
OI 路上怅前望，且行且彷徨
T1 最大公约数
T1 应该想一想就会，接下来我们讨论是怎么减去他的复杂度的。
题目的关键在于，如果根据给出的 \(a\) 推出 \(\gcd\) 的话，就会有 \(9\times 10^{10}\) 条推导关系。
而如果根据给出的 \(\gcd\) 反向找 \(a\) 的话，就只有 $10^6 \log 10^6 $ (均摊 \(\log n\) ) 条推导关系。这就是为什么反向推导会更简单的原因。
#include<bits/stdc++.h>
using namespace std;
#define fi(l,r) for(int i=l;i<=r;++i)
#define ff(i,l,r) for(int i=l;i<=r;++i)
#define ll long long
#define ly __int128
#define lp ll
#define lson(x) ((x)<<1)
#define rson(x) (lson(x)|1)
#define Lson(x) tr[lson(x)]
#define Rson(x) tr[rson(x)]
#define mod %P
#define N 300005
int n,kk,cur,amax;
struct Pi{int x,y;bool operator < (const int b){return x<b;}}a[N];
bool operator < (const int x,Pi y){return x<y.x;}
bool Pi_cmp_by_x(Pi x,Pi y){return (x.x==y.x)?x.y<y.y:x.x<y.x;}
int main(){
freopen("gcd.in","r",stdin);
freopen("gcd.out","w",stdout);
scanf("%d %d",&n,&kk);
fi(1,n){
scanf("%d",&a[i].x);
a[i].y=i;
amax=max(amax,a[i].x);
}
sort(a+1,a+n+1,Pi_cmp_by_x);
for(cur=amax;cur>=1;--cur){//分别枚举每一个 gcd
int f1=n+1,f2=0;Pi*j=a;
for(int i=cur;i<=amax;i+=cur){//在 a 中查找有没有 gcd 的倍数
j=lower_bound(j,a+n+1,i);
if(j==a+n+1)break;
if(j->x==i){
f1=min(f1,j->y),f2=max(f2,j->y);
j=upper_bound(j+1,a+n+1,i)-1;
f1=min(f1,j->y),f2=max(f2,j->y);//记录满足条件的最小和最大下标
}
}
if(f1+kk<=f2){//如果存在
printf("%d",cur);
return 0;
}
}
printf("1\n");
return 0;
}
T2 子序列
我们可以把题目转化成长度为 \(n\) 的删除序列有多少种，两种不同当且仅当有至少一个删除操作删除的字符不同。
然后我们发现左边无论怎么删都跟我右边没有关系，所以考虑分治。
先考虑
分
:
我们钦定只考虑 \([l,r]\) 区间内的数的删除方式有 \(f_{l,r}\) 种。
↓一个长度为11的01串
我们随便来一组分治，然后假定 \(L,R\) 区间已经搞定被删除掉了，即将要删除 \(this\) 所在的字符：
剩下的串是 1011，要删除第一个 1 ，合规。
我们再考虑这样的分治
我们发现将要删除一个 0，但删这个 0 和删红色 0 最终得到的删除序列是一样的，这个时候我们钦定每次只删连续区间里最后一个字符来避免重复。
if (r==n||s[i]!=s[r+1])
ans=(ans+1ll*C[r-l][i-l]*dfs(l,i-1)%mod*dfs(i+1,r))%mod;
这里的 if 语句就是用来干这个的（在最长的序列里不会重复所以所有字符都可以删除）
我们发现分治到 \(l<r\) 的情况可以直接算为 \(1\) ,而 \(l=r\) 的情况有可能是 \(0\) (如果和后面的第一个没删除的字符相同)，但也有可能是 \(1\) （如果和后面的第一个没删除的字符不同）
然后我们考虑 治
以下的红色数字是 \(L,R\) 两个区间的分别的任意一组删除序列
考虑和归并排序一样的合并方法，容易知道一共有 \(C_{|L|+|R|}^{|L|}\) 种方式来按顺序合并两个序列。中间的 1 是最后删。举个例子，合并过后的一种删除序列长这样：
到这里这道题就做完了，以下是完整代码：
(因为有的 \(f\) 算出来可能是 \(0\) , 所以 \(f\) 要初始化成 \(-1\))
#include<bits/stdc++.h>
using namespace std;
#define fi(l,r) for(int i=l;i<=r;++i)
#define ff(i,l,r) for(int i=l;i<=r;++i)
#define ll long long
#define ly __int128
#define lp ll
#define lson(x) ((x)<<1)
#define rson(x) (lson(x)|1)
#define Lson(x) tr[lson(x)]
#define Rson(x) tr[rson(x)]
#define P 1000000007
#define mod %P
#define N 405
ll f[N][N],C[N][N];
int n,s[N];
ll getf(int l,int r){
if(l>r)return 1;
if(f[l][r]!=-1)return f[l][r];
ll ret=0;
fi(l,r)
if(n==r||s[i]!=s[r+1])ret=(ret+getf(l,i-1)*getf(i+1,r)%P*C[r-l][r-i]%P)%P;
return f[l][r]=ret%P;
}
int main(){
memset(f,-1,sizeof f);
freopen("sub.in","r",stdin);
freopen("sub.out","w",stdout);
scanf("%d",&n);
char ch=getchar();while(ch!='0'&&ch!='1')ch=getchar();
fi(1,n){
s[i]=ch-'0';
ch=getchar();
}
fi(0,n){
C[i][0]=1;
ff(j,1,i)C[i][j]=(C[i-1][j]+C[i-1][j-1])%P;
}
printf("%lld\n",getf(1,n)%P);
return 0;
}