T1

SOURCE：瞎编的，但感觉应该有原题

5分：我不会。

$n,m\leq 5$：爆搜一下。

$m=2$：暴力枚举第一次的区间，然后枚举第二个区间的过程中处理一下合法位置个数即可。

$m=3$：暴力枚举前两个区间，那么你可以知道每个位置有如下三种情况：

（1）一定要被第三个区间包含。

（2）一定不能被第三个区间包含。

（3）无所谓。

我们把每个位置按情况写成$1,2,3$，那么：我的第三个区间必须得包含所有的$1$，一定不能包含所有的$2$。扫一遍就知道区间左/右端点的合法区间了。

$n,m\leq 50$：

我们考虑把这个问题转化一下模型，变成：你需要指定$m$对括号，使得每个位置被包含的次数恰好在$l_i,r_i$范围内。

那么：我们用$dp_{i,j,k}$表示当前已经考虑到了第$i$个位置，目前一共出现过$j$对括号，其中$k$对括号目前只出现了(，$j-k$对括号目前已经出现了()，的方案数。

那么，我们就可以枚举在第$i+1$个位置一共出现了几个(，几个)，来算方案数了。

这样时间复杂度是$O(nm^4)$的。

正解：

我们考虑把(和)的流程分开：在每个位置，先处理)，再处理(，即可。

也就是：$dp1_{i,j,k}$表示我该考虑在$i$处添加右括号时的方案，$dp2_{i,j,k}$表示我该考虑在$i$处添加左括号时候的方案。

具体转移不表，复杂度$O(nm^3)$，但实际上，这个dp在满数据下只需要3e8次循环，所以开了$3s$：

#include<bits/stdc++.h>
#define maxn 305
#define ll long long
#define mod 998244353 
using namespace std;
ll C[maxn][maxn];
void init()
{
	C[0][0]=1;
	for (int i=1;i<maxn;i++)
		for (int j=0;j<=i;j++)
		{
			if (i==1 || j==0) C[i][j]=1;
			else C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
		}
}
int n,m;
int l[maxn],r[maxn];
ll dp1[105][maxn][maxn],dp2[105][maxn][maxn];
void add(ll &x,ll y) {x=(x+y)%mod; return;}
int main()
{
	init(); 
	cin>>n>>m;
	for (int i=1;i<=n;i++) cin>>l[i];
	for (int i=1;i<=n;i++) cin>>r[i];
	dp2[0][0][0]=1; //dp2表示考虑完（）的结果
	for (int i=0;i<=n;i++)
	{
		//首先转移dp1到dp2，再转移dp2到下一个dp1 
		for (int j=0;j<=m;j++)  
		for (int k=l[i];k<=r[i];k++) //左括号个数 
		if (dp1[i][j][k])
		{
			for (int t=0;t<=k;t++) //在此处添加t个右括号
			{
				add(dp2[i][j][k-t],dp1[i][j][k]*C[k][t]);
			}
		}
		for (int j=0;j<=m;j++)  
		for (int k=0;k<=j;k++) //左括号个数 
		if (dp2[i][j][k])
		{
            //在i+1处添加t个左括号，
            //需要满足0<=t+k<=j以及l[i+1]<=t+k<=r[i+1]
			for (int t=max(0,l[i+1]-k);t<=min(m-j,r[i+1]-k);t++)
			{
				add(dp1[i+1][j+t][k+t],dp2[i][j][k]*C[m-j][t]);
			}
		}
	}
	cout<<dp2[n][m][0]<<endl;
}

T2

SOURCE：CF1548B

20分：

考虑枚举左端点$l$，向右维护哪些$m$是可行的，以及对应的$a_i\mod m$是多少即可。

复杂度$O(n^2a)$。

40分：

我们考虑先枚举$m$是多少，把所有数字变成$a_i\mod m$，接下来的问题就变成：给你一个序列，问最长的全相同的序列有多长了。

随便怎么做，复杂度$O(na)$。

70分：

考虑$a$和$b$在什么情况下可以模$m$相同？

我们换种表示：$a=k_a m +t,b=k_b m +t$。

换句话说，$a-b=(k_a-k_b)m$一定是$m$的倍数。

也就是说，只要选择的$m$，是$a,b$差的倍数，就一定能满足条件。（其实也可以打表看出来）。

那么我们维护一个差分数组$b_i$。

问题就变成：我最多能选多长一段$b$，使得这一段的$\gcd$非$1$了。

预处理$g_{i,j}$表示从$i$出发，向右$2^j$个元素的$gcd$，则这个问题可以通过枚举左端点$l$，倍增右端点$r$来完成。

ll len=1;
for (int i=1;i<=n-1;i++)
{
    ll gg=g[i][0],now=i;
    for (int j=21;j>=0;j--)
    if (__gcd(gg,g[now][j])!=1)
    {
        gg=__gcd(gg,g[now][j]);
        now=now+(1<<j);
        if (now>=n) {now=n; break;}
    }
    len=max(len,now-i+1);
}

时间复杂度$O(n\log n\log a)$，跑的非常慢。

100分：

我们很想双指针，但是双指针不好删元素。

一个脑洞大开的方法是，我对于当前维护的区间$[l,r]$，我找一个位置$mid$。

我来维护$a_i(l\leq i\leq mid)$表示$\gcd(a_i,...,a_{mid})$。

维护一个$b_i(mid\leq i\leq r)$表示$gcd(b_{mid},...,b_r)$。

这样，对于当前区间$[l,r]$，他们的$\gcd$就是$\gcd(a_l,b_r)$。

对于添加$r+1$，只需要$O(log a)$的速度。

对于删除$l$，只需要$O(1)$的速度。

当$l$超过我们的$mid$时，我们就重新选定$mid$为$r$，然后重构数组$a,b$。

复杂度非常好分析，当$mid$从$x$变成$y$的时候，我只需要重构$[x,y]$内的信息，所以总复杂度是$O(n\log a)$的。非常快。

//洛谷上复制来的
#include<cstdio>
typedef unsigned ui;
typedef unsigned long long ull;
const ui M=2e6+5;
ui T,n;ull a[M],f[M];
inline ull gcd(const ull&a,const ull&b){
	return b?gcd(b,a%b):a;
}
signed main(){
	T=1;
	ui i,j,l,mid,ans;
	while(T--){
		scanf("%u",&n);l=mid=1;ans=0;
		for(i=1;i<=n;++i)scanf("%llu",a+i),a[i-1]=a[i-1]>a[i]?a[i-1]-a[i]:a[i]-a[i-1];
		for(i=1;i<n;++i){
			f[i]=i==1||i-1==mid?a[i]:gcd(f[i-1],a[i]);
			while(l<=mid&&gcd(f[l],f[i])==1)++l;
			if(l>mid){
				f[i]=a[mid=i];
				for(j=i-1;j>=l;--j)f[j]=gcd(a[j],f[j+1]);
				while(l<=i&&f[l]==1)++l;
			}
			if(i-l+1>ans)ans=i-l+1;
		}
		printf("%u\n",++ans);
	}
}

T3

SOURCE：CF1548C加强了一点

直接考虑正解吧。

我们定义$f_{i,x}=\sum_{j=1}^nC_{tj+i}^x$。

那么对于每次询问$x$，要的其实就是$f_{0,x}$。

现在我们知道：

$\sum_{i=0}^{t-1}f_{i,x}=\sum_{i=t}^{tn}C_i^x$

以及一个组合恒等式：

$\sum_{i=1}^{tn}C_i^x=C_{tn+1}^{x+1}$。（式子1）

以及另外一个简单推理：

$f_{i,x}=\sum_{j=1}^nC_{tj+i}^x$

$f_{i-1,x-1}=\sum_{j=1}^n C_{tj+i-1}^x$

$f_{i-1,x}=\sum_{j=1}^n C_{tj+i-1}^{x-1}$

显然的：

$f_{i,x}=f_{i-1,x-1}+f_{i-1,x}$（式子2）

于是，我们可以考虑按$x$从小到大，依次求出$f_{i,x}$。

具体怎么求呢？

当我们要求$f_{i,x}$的时候，我们假设$f_{i,x-1}$已经求出来了。

那么：我可以根据式子1和式子2，列一个$t$元一次方程组来高斯消元，这样对于每一个$x$，复杂度是$t^3$的。总复杂度是$nt\times t^3$的。

反正$t=3$是完全可以做出来的。

怎么求正解呢？答案就是代入消元了。

我们用$f_{0,x}$来表示$f_{1,x}$，再继续用$f_{0,x}$来表示$f_{2,x}$，...，这么表示完以后，把他们加起来，就变成了$af_{0,x}+b=\sum_{i=t}^{tn}C_i^x$了，就可以解出$f_{0,x}$以及其他变量了。

复杂度$O(nt^2)$。给$5$秒是因为我写的有点屎，懒得卡常，以及要给$n^3$高斯消元的分数（虽然我感觉没什么人能想到$O(t^3)$但想不到$O(t)$。

for (int i=0;i<t;i++) f[0][i]=n;
for (int i=1;i<=t*n;i++)
{
    for (int j=0;j<=t;j++) memset(tmp[j].v,0,sizeof(tmp[j].v));
    tmp[0].v[0]=1;
    for (int j=1;j<t;j++)
    {
        add(tmp[j],tmp[j-1]);
        add(tmp[j].v[1],f[i-1][j-1]);
    }
    for (int j=1;j<t;j++) add(tmp[0],tmp[j]);

    ll tot=cc(t*n+t,i+1);
    for (int j=1;j<t;j++) tot=tot-cc(j,i); 
    tot=tot-tmp[0].v[1];
    tot=(tot%mod+mod)%mod;
    ll ni=pw(tmp[0].v[0],mod-2);
    f[i][0]=ni*tot%mod;

    for (int j=1;j<t;j++)
    {
        f[i][j]=((f[i][0]*tmp[j].v[0]+tmp[j].v[1])%mod+mod)%mod;
    }
}

T4

SOURCE：CF1548E

懒得再写一遍题解，大概嘴一下思路：

就是说，我们对于每一个黑色连通块，找到一个黑点来代表这个连通块。

我们只需要计算有多少个这样的黑色代表点即可。

对于每个连通块，我们认为具有代表性的连通块是$a_i+b_j$最小的那一个。如果有多个，则按$i$为第一关键字，$j$为第二关键字选取。

那么，记$L_i,R_i$为$i$左侧第一个$a_{L_i}$小于等于$a_i$的位置，以及右侧第一个$a_{R_i}$小于$a_i$的位置。$U_i,D_i$同理。

那么，假设$(i,j)$不是代表元，那必然可以走到刚求出来的上下左右对应的四个位置之一。（这个不难证明）

反过来来说，如果$(i,j)$是代表元，则走不到。

对应成条件是：

我们求一下$i$向左右走到对应位置，理想情况下中间经过的最大的$a+b$，那么走不到就相当于$a_i+\min(\max(b_{[{L_i},i]}),\max(b_{[i,R_i]}))>x$

上下同理。

以及$a_i+b_j\leq x$。

一共三个不等式，但在确定了$i$的时候只涉及$j$对应的两个值。就是【模板-二维偏序】了，树状数组即可。

#include<bits/stdc++.h>
using namespace std;
inline int readint(){
	int x=0;
	bool f=0;
	char c=getchar();
	while(!isdigit(c)&&c!='-') c=getchar();
	if(c=='-'){
		f=1;
		c=getchar();
	}
	while(isdigit(c)){
		x=x*10+c-'0';
		c=getchar();
	}
	return f?-x:x;
}
const int maxn=2e5+5;
int n,m,x,a[maxn],b[maxn],s[maxn],tp=1,mx[maxn];
int prea[maxn],suca[maxn],preb[maxn],sucb[maxn];
inline int lowbit(int x){
	return x&-x;
}
int c[maxn];
void modify(int x,int k){
	while(x<maxn){
		c[x]+=k;
		x+=lowbit(x);
	}
}
int query(int x){
	int s=0;
	while(x){
		s+=c[x];
		x-=lowbit(x);
	}
	return s;
}
vector<int> qa[maxn],qb[maxn];
int main(){
	n=readint();
	m=readint();
	x=readint();
	for(int i=1;i<=n;i++) a[i]=readint();
	for(int i=1;i<=m;i++) b[i]=readint();
	mx[0]=maxn-1;
	for(int i=1;i<=n;i++){
		while(a[i]<a[s[tp-1]]){
			mx[tp-2]=max(mx[tp-2],mx[tp-1]);
			tp--;
		}
		prea[i]=max(mx[tp-1],a[i]);
		s[tp]=i;
		mx[tp++]=a[i];
	}
	tp=1;
	for(int i=1;i<=m;i++){
		while(b[i]<b[s[tp-1]]){
			mx[tp-2]=max(mx[tp-2],mx[tp-1]);
			tp--;
		}
		preb[i]=max(mx[tp-1],b[i]);
		s[tp]=i;
		mx[tp++]=b[i];
	}
	s[0]=n+1;
	tp=1;
	for(int i=n;i>0;i--){
		while(a[i]<=a[s[tp-1]]){
			mx[tp-2]=max(mx[tp-2],mx[tp-1]);
			tp--;
		}
		suca[i]=max(mx[tp-1],a[i]);
		s[tp]=i;
		mx[tp++]=a[i];
	}
	s[0]=m+1;
	tp=1;
	for(int i=m;i>0;i--){
		while(b[i]<=b[s[tp-1]]){
			mx[tp-2]=max(mx[tp-2],mx[tp-1]);
			tp--;
		}
		sucb[i]=max(mx[tp-1],b[i]);
		s[tp]=i;
		mx[tp++]=b[i];
	}
	for(int i=1;i<=n;i++) if(a[i]<=x) qa[x-a[i]].push_back(i);
	for(int i=1;i<=m;i++) qb[min(preb[i],sucb[i])].push_back(i);
	long long ans=0;
	for(int i=maxn-1;i>0;i--){
		for(int j:qa[i])
			ans+=query(x-a[j])-query(max(x-min(prea[j],suca[j]),0));
		for(int j:qb[i]) modify(b[j],1);
	}
	printf("%lld\n",ans);
	return 0;
}