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?S_n^i$$

為了求解答案，我們設$su{m}_j[n]={\sum }_{i=1}^n{i}^j?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?S_{n?1}^i\\ & \\ & 帶入遞推式S_n^m=(n?1)\times S_{n?1}^m+S_{n?1}^{m?1}:\\ & \\ & =\sum _{i=1}^{n}i?[(n?1)S_{n?1}^i+S_{n?1}^{i?1}]\\ & \\ & =(n?1)\sum _{i=1}^{n}i?S_{n?1}^i+\sum _{i=1}^{n}i?S_{n?1}^{i?1}\\ & \\ & =(n?1)su{m}_1[n?1]+\sum _{i=0}^{n?1}(i+1)?S_{n?1}^i\\ & \\ & =(n?1)su{m}_1[n?1]+\sum _{i=1}^{n?1}i?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?su{m}_1[n?1]+su{m}_0[n?1]\end{array}\text{\hspace{1em}?}$$
因此我們可以完全類比推導過程得出$su{m}_j[n]$的公式：
$$\begin{array}{rl}& su{m}_j[n]=\sum _{i=1}^n{i}^j?S_n^i\\ & \\ & =\sum _{i=1}^n{i}^j?[(n?1)S_{n?1}^i+S_{n?1}^{i?1}]\\ & \\ & =(n?1)su{m}_j[n?1]+\sum _{i=1}^n{i}^j?S_{n?1}^{i?1}\\ & \\ & =(n?1)su{m}_j[n?1]+\sum _{i=0}^{n?1}(i+1{)}^j?S_{n?1}^i\\ & \\ & =(n?1)su{m}_j[n?1]+\sum _{i=1}^{n?1}\sum _{k=0}^j{C}_j^k?i^k?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?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}\text{\hspace{1em}?}$$
由此我們可以在$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+?+C_{m+n?1}^m{x}^m+?={\sum }_{i=0}^{\infty }{C}_{i+n?1}^i{x}^i$
• 構造多項式$F(x)?F(x)?\dots ?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!?m!}=\frac{(m+t)(m+t?1)???(t+1)}{m!}\end{array}\text{\hspace{1em}?}$$
分子可以$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(); }
}