L.最小括号串

#数组操作 #贪心

题目

思路

感谢Leratiomyces大佬赛时的提示，否则估计还一直签不了到（）

首先，贪心地构造出最优情况：数组左半部分全是(，右半部分全是)，随后通过判断给定的区间中是否包含(来决定是否调整当前序列。

对给定的区间按照左端点降序排序，这样就可以从右往左有序遍历所有区间。

设置两个指针$i{d}_l,i{d}_r$：

• $i{d}_l$指向未被调换的(中最右的(的下标
• $i{d}_r$指向经过调换后的(中最左的(的下标

从右往左有序遍历所有区间：

• 如果当前区间右端点$r$在$i{d}_r$左侧，那么说明当前区间$[l,r]$中一定没有(，因此需要调度一个(前往$l$位置（尽量保证字典序小），即$swap(ans[i{d}_l],ans[l])$
• 调度前需要注意$i{d}_l$是否为0，即序列左端是否还剩余(。如果$i{d}_l==0$而仍然需要调度(，那么必然是不合法的，输出-1

最后不要忘了遍历整个序列判断是否会存在)(的非法情况

代码实现

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<unordered_set>
#include<queue>
using namespace std;
using ll = long long;
#define rep(i, a, b) for(ll i = (a); i <= (b); i++)
#define per(i, a, b) for(ll i = (a); i >= (b); i--)
#define mid ((l+r)>>1)
#define see(stl) for(auto&ele:stl)cout<<ele<<" "; cout<<'\n';
const int N=1e5+5;
int n,m;
struct lr{int l,r;bool operator<(const lr&t)const{return l>t.l;}
};
void solve() {cin>>n>>m;n*=2;vector<lr>b(m+1);    vector<char>ans(n+1);rep(i,1,m){int l,r;cin>>l>>r;b[i]={l,r};}rep(i,1,n){if(i<=n/2)ans[i]='(';else ans[i]=')';}sort(b.begin()+1,b.begin()+1+m);int idl=n/2,idr=n+1;rep(i,1,m){int l=b[i].l,r=b[i].r;if(r<idr){if(idl<1){cout<<-1<<'\n';return;}swap(ans[idl],ans[l]);idr=l;idl--;}}int cntl=0,cntr=0;rep(i,1,n){if(ans[i]=='(')cntl++;else cntr++;if(cntr>cntl){cout<<-1<<'\n';return;}}rep(i,1,n)cout<<ans[i];cout<<'\n';
}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {solve();}return 0;
}

---

C.栈

#数学 #组合数 #斯特林数

题目

思路

提供一种纯数学的方法：

设$S_n^m$为长度为$n$的所有排列中$size$为$m$的数量
易知${\sum }_{i=1}^n{S}_n^i=n!$，即排列数$A_n^n$

接下来可以找出他的递推：

• 当数字$n$不位于排列的最后一位时，$stack$的$pop$功能必定会将其$pop$掉，即数字$n$不产生贡献。数字$n$不位于最后一位的可能有$n-1$种，那么就可以将此时的情况等价于$长度为n-1的所有排列中size为m的数量$，即$(n-1)\times S_{n-1}^m$
• 当数字$n$位于排列的最后一位时，其必然对$size$产生$1$的贡献，那么就可以将此时的情况等价于$长度为n-1的所有排列中size为m-1的数量$，即$S_{n-1}^{m-1}$
  综上：
  $$S_n^m=(n-1)\times S_{n-1}^m+S_{n-1}^{m-1}$$
  则答案所求即：
  $$\sum _{i=1}^n{i}^3\cdot S_n^i$$

为了求解答案，我们设$su{m}_j[n]={\sum }_{i=1}^n{i}^j\cdot S_n^i$，其中：

• $su{m}_0[n]={\sum }_{i=1}^n{S}_{n^i}=n!$
• 所求答案即$su{m}_3[n]$

接下来我们来研究$su{m}_j$之间的递推：
$$\begin{array}{rl}su{m}_1[n]& =\sum _{i=1}^{n}i\cdot S_{n-1}^i\\ & \\ & 带入递推式S_n^m=(n-1)\times S_{n-1}^m+S_{n-1}^{m-1}:\\ & \\ & =\sum _{i=1}^{n}i\cdot [(n-1)S_{n-1}^i+S_{n-1}^{i-1}]\\ & \\ & =(n-1)\sum _{i=1}^{n}i\cdot S_{n-1}^i+\sum _{i=1}^{n}i\cdot S_{n-1}^{i-1}\\ & \\ & =(n-1)su{m}_1[n-1]+\sum _{i=0}^{n-1}(i+1)\cdot S_{n-1}^i\\ & \\ & =(n-1)su{m}_1[n-1]+\sum _{i=1}^{n-1}i\cdot S_{n-1}^i+\sum _{i=1}^{n-1}{S}_{n-1}^i\\ & \\ & =(n-1+1)su{m}_1[n-1]+su{m}_0[n-1]\\ & \\ su{m}_1[n]& =n\cdot su{m}_1[n-1]+su{m}_0[n-1]\end{array}$$
因此我们可以完全类比推导过程得出$su{m}_j[n]$的公式：
$$\begin{array}{rl}& su{m}_j[n]=\sum _{i=1}^n{i}^j\cdot S_n^i\\ & \\ & =\sum _{i=1}^n{i}^j\cdot [(n-1)S_{n-1}^i+S_{n-1}^{i-1}]\\ & \\ & =(n-1)su{m}_j[n-1]+\sum _{i=1}^n{i}^j\cdot S_{n-1}^{i-1}\\ & \\ & =(n-1)su{m}_j[n-1]+\sum _{i=0}^{n-1}(i+1{)}^j\cdot S_{n-1}^i\\ & \\ & =(n-1)su{m}_j[n-1]+\sum _{i=1}^{n-1}\sum _{k=0}^j{C}_j^k\cdot i^k\cdot S_{n-1}^i\\ & \\ & =(n-1)su{m}_j[n-1]+\sum _{k=0}^j{C}_j^k\sum _{i=1}^{n-1}{i}^k\cdot S_{n-1}^i\\ & \\ su{m}_j[n]& =(n-1)su{m}_j[n-1]+\sum _{k=0}^{j}su{m}_k[n-1]\end{array}$$
由此我们可以在$o(n)$的复杂度下递推得到$su{m}_3[n]$

代码实现

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<unordered_map>
#include<set>
using namespace std;
using ll = long long;
#define rep(i, a, b) for(ll i = (a); i <= (b); i ++)
#define per(i, a, b) for(ll i = (a); i >= (b); i --)
const int MOD = 998244353;
const int N = 5e5 + 5;ll ans[N], sum3[N], sum2[N], sum1[N], sum0[N];void precompute() {sum0[1] = 1;sum1[1] = 1;sum2[1] = 1;sum3[1] = 1;ans[1] = 1;  for (int n = 2; n < N; ++n) {sum0[n] = (n * sum0[n-1]) % MOD;sum1[n] = (n * sum1[n-1] + sum0[n-1]) % MOD;sum2[n] = (n * sum2[n-1] + 2 * sum1[n-1] + sum0[n-1]) % MOD;sum3[n] = (n * sum3[n-1] + 3 * sum2[n-1] + 3 * sum1[n-1] + sum0[n-1]) % MOD;       ans[n] = sum3[n];}
}int main() {ios::sync_with_stdio(false);cin.tie(0);precompute();int T;cin >> T;while (T--) {int n;cin >> n;cout << ans[n] << '\n';}return 0;
}

---

K. 最大gcd

#数学 #gcd #差分

题目

思路

已知gcd具有特殊性质：
$$gcd(a_1,a_2,\dots ,a_n)=gcd(a_1,a_2-a_1,a_3-a_2,\dots ,a_n-a_{n-1})$$
设差分数组$b[N],b[i]=a[i]-a[i-1]$

则对于区间$[l,r]$内每个数都加$k$相当于对$b[l]+=k,b[r+1]-=k$

• 首先讨论整个数组都$+k$的情况：
  • 操作$b[1]+=k$即可（$b[r+1]$不存在）
  • 此时的gcd为$gcd(b_1+k,b_2,\dots ,b_n)$
  • 必定存在$k$使得$gcd(b_2,b_3,\dots ,b_n)|(b_1+k)$
  • 因此该情况的gcd记为$g_1=gcd(b_2,b_3,\dots ,b_n)$
• 接下来讨论局部$+k$的情况：
  • 由于是局部操作，所以$b_1,b_n$这两个的其中一个必定不会被$+k$，因此枚举$b_1,b_n$的所有因数$f$
  • 若所有的$b_i$都为$f$的倍数，那么当前的$f$一定是合法的gcd
  • 若只有一个$b_i$不是$f$的倍数，那么一定存在一个$k$使得$f|(b_i+k)$，当前的$f$也是合法的
  • 若超过两个$b_i$不是$f$的倍数，那么无论怎么操作都不可能使得整个数组的gcd为$f$
  • 若只有两个$b_i$不是$f$的倍数，那么需要特殊判断。在此提供两种判断方法：
    • 方法一：
      • 设不是$f$的两个数为$b_1,b_2$，则$b_1=t_1\times f+b_1\%f,b_2=t_2\times f+b_2\%f$
      • 令$k=b_1\%f$，则$b_1-k=t_1\times f$为$f$的倍数；
      • $b_2+k=t_2\times f+b_1\%f+b_2\%f$要为$f$的倍数，则必有$(b_1\%f+b_2\%f)\%f=0$
      • 因此可以通过判别式$(b_1\%f+b_2\%f)\%f=0$来确定两个$b_i$是否合法
    • 方法二：
      • 设不是$f$的两个数为$b_1,b_2$且$b_1-k,b_2+k$为$f$的倍数，则有$b_1\equiv k(\mathrm{mod}f),b_2\equiv (-k)(\mathrm{mod}f)$
      • 两式相加得$(b_1+b_2)\equiv 0(\mathrm{mod}f)$，即$(b_1+b_2)\%f=0$
      • 因此可以通过判别式$(b_1+b_2)\%f=0$来判断两个$b_i$是否合法

特别需要注意的是，由于差分可能会导致负数，所以gcd函数返回的时候需要加绝对值
这与给传入的变量加绝对值是完全不一样的操作！

代码实现

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<unordered_map>
#include<set>
using namespace std;
using ll = long long;
#define rep(i, a, b) for(ll i = (a); i <= (b); i ++)
#define per(i, a, b) for(ll i = (a); i >= (b); i --)
//#define see(stl) for(auto&ele:stl)cout<<ele<<" "; cout<<'\n';
const ll inf = 1e7 + 5;
// #define int ll
const int N=1e5+5;ll gcd(ll a,ll b){if(!b)return abs(a);return gcd(b,a%b);
}int a[N],b[N];
void eachT() {int n;cin>>n;bool same=1;int g1;rep(i,1,n){cin>>a[i],b[i]=(a[i]-a[i-1]);if(i==2)g1=b[2];if(i>=3)g1=gcd(g1,(b[i]));if(i>=2&&a[i]!=a[i-1])same=0;}if(same){cout<<0<<'\n';return;}if(n==2){cout<<max(a[1],a[2])<<'\n';return;}set<int>fac;for(int i=1;i*i<=a[1];i++){if(a[1]%i==0)fac.insert(i),fac.insert(a[1]/i);}for(int i=1;i*i<=a[n];i++){if(a[n]%i==0)fac.insert(i),fac.insert(a[n]/i);}int cnt,ans=g1;for(auto&f:fac){int mod=0;cnt=0;  rep(i,2,n)if(b[i]%f!=0)cnt++,mod+=b[i]%f;if(cnt<=1){ans=max(ans,f);      }if((cnt==2)&&(mod%f==0)){ans=max(ans,f);}}cout<<ans<<'\n';
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);ll t = 1;cin >> t;while (t--) { eachT(); }
}

---

D.漂亮矩阵

#数学 #组合数 #广义二项式定理 #FFT

题目

思路

设$B_{i,j}=A_{i,j+1}-A_{i,j}$，则有$B_{i,j}\ge B_{i+1,j}$且${\sum }_{j=1}^n{B}_{i,j}\le m$
因此有${\sum }_{j=1}^n{B}_{i+1,j}\le {\sum }_{j=1}^n{B}_{i,j}\le {\sum }_{j=1}^n{B}_{1,j}\le m$
所以只需要满足${\sum }_{1,j}^n{B}_{1,j}\le m$且每列的$B$值单调不增即可

设$B_{1,i}=x$，一列共有$n$个元素，求这一列开头为$x$且后续单调不增的所有情况数：

• 假设有$x$块隔板$l_i,i\in [0,x]$，若$l_{i-1}$到$l_i$间有$k$个数，则令这$k$个数为$i$
• 由于开头已经固定为$x$，只能对剩下的$n-1$个数进行操作，$n-1$个数提供$n-1$个空位，再加上$x$个隔板自己的位置，相当于一共$x+n-1$个空位中放入$x$个隔板，即$C_{x+n-1}^x$
  

接下来利用生成函数来构造总和不超过$m$的所有情况数：

• 构造函数$F(x)=C_{0+n-1}^0{x}^0+C_{1+n-1}^1{x}^1+\cdots +C_{m+n-1}^m{x}^m+\cdots ={\sum }_{i=0}^{\infty }{C}_{i+n-1}^i{x}^i$
• 构造多项式$F(x)\cdot F(x)\cdot \dots \cdot F(x)=F(x{)}^{n-1}$，相当于除了第一列以外的$n-1$列的所有情况。多项式$F(x{)}^{n-1}$中的前$m$项的系数之和即为总和不超过$m$的所有情况数

此时可以用$FFT$来快速得出答案，复杂度$o(n\log n)$

但是其实还可以用广义二项式定理进一步化简：
广义二项式定理实际上就是将组合数的定义域拓宽到了整个实数域
$$\begin{array}{rl}& F(x)=\sum _{i=0}^{\infty }{C}_{i+n-1}^i{x}^i=(1-x{)}^{-n}(广义二项式定理)\\ & \\ & F(x{)}^{n-1}=(1-x{)}^{-n(n-1)}\\ & \\ & 令t=n(n-1)\\ & \\ & 则F(x{)}^{n-1}=(1-x{)}^{-t}=\sum _{i=0}^{\infty }{C}_{i+t-1}^i{x}^i=\sum _{i=0}^{\infty }{C}_{i+t-1}^{t-1}{x}^i\\ & \\ & 则其前m项的系数和为\sum _{i=0}^m{C}_{i+t-1}^{t-1}=C_{m+t}^t\\ & \\ & 即求\frac{(m+t)!}{t!\cdot m!}=\frac{(m+t)(m+t-1)\cdot \cdot \cdot (t+1)}{m!}\end{array}$$
分子可以$o(m)$暴力算出，分母可以$o(m)$预处理逆元算出，总复杂度为$o(m)$

代码实现

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<unordered_map>
#include<set>
using namespace std;
using ll = long long;
#define rep(i, a, b) for(ll i = (a); i <= (b); i ++)
#define per(i, a, b) for(ll i = (a); i >= (b); i --)
//#define see(stl) for(auto&ele:stl)cout<<ele<<" "; cout<<'\n';
const ll inf = 1e7 + 5;
// #define int ll
const int N=1e5+5;ll mod=998244353;
ll qpow(ll a, ll b) {a %= mod; ll res = 1;while (b) {if (b % 2) { res *= a, res %= mod; }a *= a, a %= mod, b /= 2;}return res%mod;
}
vector<ll>a, inv;
void inv0(ll len) {a.resize(len + 1), inv.resize(len + 1);a[0] = 1, inv[0] = 1;rep(i, 1, len) {a[i] = a[i - 1] * i % mod;inv[i] = qpow(a[i], mod - 2);}
}void eachT() {ll n,m;cin>>n>>m;ll ans=1;rep(i,1,m){ans*=(n*(n-1)+i)%mod;ans%=mod;}ans*=inv[m];ans%=mod;cout<<ans<<'\n';
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);inv0(5e5);ll t = 1;//cin >> t;while (t--) { eachT(); }
}