• CF2146F Bubble Sort
    设 \(f_i=\sum_j^i[a_j>a_i]\) ，则一个序列冒泡排序的总轮数是 \(\max f_i\) 。
    注意到 \(f\) 和 \(a\) 是双射关系，所以只需要对 \(f\) 计数即可。
    对于一个限制 \((k,l,r)\) ，即要求 \(\max_{i=1}^lf_i\leq k\) 且 \(f_{r+1}>k\) ，考虑如果 \(r=+∞\) ，那计数就简单多了，于是我们用容斥做，把一个这样的限制拆成 \((k,l,+∞)\) 和 \((k,r,+∞)\) 前者系数为 \(1\) ，后者为 \(-1\) 。于是就可以 \(dp\) 了。
    先按照 \(k\) 从小到大排序取消后效性，设 \(dp_{i,j}\) 表示考虑完前 \(i\) 个限制，占用了前 \(j\) 个位置的方案数，直接转移即可，离散化完复杂度是 \(O(\sum m^2logn)\) 。
点击查看代码
#include
#include
#include
#include
#include
#define ll long long
using namespace std;
const int N=1e6+6;
const int M=1005;
const int Mod=998244353;
int n,m;
struct _{int l,r,k;
}a[M];
int b[M<<1],len;
ll f[M<<1],g[M<<1];
ll inv[N],fac[N];
inline ll ksm(ll x,ll y){ll res=1;while(y){if(y&1) res=res*x%Mod;y>>=1;x=x*x%Mod;}return res;
}
inline ll calc(int l,int r,int k){// return 0;if(k<=l){return ksm(k,r-l);}if(r<=k){return fac[r]*inv[l]%Mod;}return fac[k]*inv[l]%Mod*ksm(k,r-k)%Mod;
}
void solve(){cin>>n>>m;len=0;b[++len]=0;for(int i=1;i<=m;i++){cin>>a[i].k>>a[i].l>>a[i].r;a[i].r++;b[++len]=a[i].l;b[++len]=a[i].r;}sort(a+1,a+m+1,[](const _ &x,const _ &y){return x.kn) continue;if(jn) break;ans=(ans+f[i]*calc(b[i],n,n)%Mod)%Mod;}cout<=0;i--) inv[i]=inv[i+1]*(i+1)%Mod;int T;cin>>T;while(T--) solve();return 0;
}
  • CF1943D2 Counting Is Fun (Hard Version)
    限制太麻烦不好做，考虑先转化。显然一个序列合法的必要条件是 \(\forall \ i,a_i\leq a_{i-1}+a_{i+1}\) ，我们大胆猜测他是充分的，证明也简单，感性理解一下就是，扩展一次操作的大小比缩小它要简单得多。
    这样我们直接盯着这一个条件计数就行了，考虑 \(dp\) 。我们直接设 \(dp_{i,j}\) 表示“考虑到下标 \(i\) ，前 \(i-1\) 个位置都合法，\(a_i=j\) ”的方案数。为什么不需要考虑 \(a_i\) 的合法性呢，因为此题有个重要的性质是不可能同时出现相邻两个 \(a_i\) 都不合法，所以我们在保证 \(a_{i-1}\) 的合法性时，需要用到 \(dp_{i-2,k}\) ，但不需要考虑 \(a_{i-2}\) 的合法性。转移过程，直接用所有方案减去不合法的方案即可。
点击查看代码
#include
#include
#include
#include
#include
#define ll long long
using namespace std;
const int N=3005;
int n,K;
int Mod;
ll f[N][N];
ll sum[N][N];
void solve(){cin>>n>>K>>Mod;f[0][0]=1;for(int i=0;i<=K;i++) sum[0][i]=1;for(int i=1;i<=n+1;i++){ll tmp=0;f[i][K]=sum[i-1][K];for(int j=K-1,k=0;j>=0;j--,k++){if(i>1) tmp=(tmp+sum[i-2][k])%Mod;f[i][j]=(sum[i-1][K]-tmp+Mod)%Mod;}sum[i][0]=f[i][0];for(int j=1;j<=K;j++) sum[i][j]=(sum[i][j-1]+f[i][j])%Mod;}cout<>T;while(T--) solve();return 0;
}
  • AT_arc199_c [ARC199C] Circular Tree Embedding
    看起来非常麻烦，必须手玩一下探索性质。发现题目限制等价于“每个子树在所有排列中对应的集合是连续的”，证明起来非常简单，由于是树所以圆上每个点都要往外连边，如果存在一个点的左右两边在它的子树内而不与它连边，那它就被封闭了。这样就非常简单了，首先预处理每个集合能不能成为一棵子树，我们通过置换令 \(P_{1,i}=i\) ，这样每棵子树就都是一个区间了，在后面的序列里判断就行，我用 \(ST\) 表维护的。
    剩下的就是区间 \(dp\) 对树进行计数了。我们钦定 \(1\) 为根，这样就消除了环的限制。设 \(f_{l,r}\) 表示区间 \([l,r]\) 形成一棵有根树的方案数，\(g_{l,r}\) 表示区间 \([l,r]\) 形成一个森林的方案数（用来形成 \(f\) 中的儿子们），两个数组一块转移即可。复杂度 \(O(n^3)\) 。
点击查看代码
#include
#include
#include
#include
#include
#define ll long long
using namespace std;
const int N=505;
const int Mod=998244353;
int n,m;
int p[N];
int mn[N][11],mx[N][11];
int id[N];
inline int cmin(int l,int r){int len=__lg(r-l+1);return min(mn[l][len],mn[r-(1<>n>>m;for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){vis[i][j]=1;}}for(int i=1;i<=n;i++){cin>>id[i];}for(int j=2;j<=m;j++){for(int i=1;i<=n;i++) cin>>p[id[i]],p[id[i]]--;int delta=p[1];for(int i=1;i<=n;i++) mn[i][0]=mx[i][0]=p[i]=(p[i]-delta+n)%n;// for(int i=1;i<=n;i++) cout<

r-l) vis[l][r]=0;}}}for(int i=0;i<=n;i++) f[i][i]=g[i][i]=f[i+1][i]=g[i+1][i]=1;for(int len=2;len<=n;len++){for(int l=1,r=len;r<=n;l++,r++){if(vis[l][r]){for(int t=l;t<=r;t++){f[l][r]=(f[l][r]+g[l][t-1]*g[t+1][r]%Mod)%Mod;}}for(int t=l;t<=r;t++){g[l][r]=(g[l][r]+f[l][t]*g[t+1][r]%Mod)%Mod;}}}cout<

  • AT_agc076_b [AGC076B] Split and Reverse
    神秘构造，方法想鸽了。
    重要的一点就是看到输出具体方案，\(n\leq 250000\) ，猜测总次数不会很多，大胆猜测 + 爆搜可以发现答案在 \({0,1,2}\) 中，再去考虑根据答案进行分类，排除最简单的 \({0,1}\)，处理更复杂的 \(2\) 即可。
点击查看代码
鸽
  • AT_arc124_e [ARC124E] Pass to Next
    神仙 \(dp\) 题。
    看起来很混乱，首先考虑对答案去重。由于最初序列是给定的，那么每个操作序列就对应了一个结果序列，但是会有重复情况，就是整体 \(+1\) 或 \(-1\) 的情况。这样我们对于每个结果序列对应的一组操作序列，只保留其中存在一个人不传球的那种情况，也就是疯狂整体 \(-1\) 直到有一个值变为 \(0\) 为止，这样就一一对应了。
    这样枚举操作序列就看起来比枚举结果序列要有道理多了。考虑最后答案的形式，乘积的和。非常经典的组合意义转化：原题转化为在每种方案中，每个人从自己的球堆中选出一个球的方案数的和。
    这样题目一下子就豁然开朗了。我们考虑枚举每个人选自己原来的球还是上一个人给的球。具体的，我们设 \(dp_{i,0}\) 表示第 \(i\) 个人选前一个人给的球，前 \(i-1\) 个人的方案数， \(dp_{i,1}\) 表示第 \(i\) 个人选自己的球，前 \(i\) 个人的方案数。
    为什么这个状态这么抽象？是因为一个人如果选自己原本的球，和他传递给下一个人的球的数量密切相关，而考虑一个人的时候需要知道上一个人传给他多少球。这两个数量是同一个要枚举的值，我们需要放在一次转移中考虑，所以延迟他的选择/贡献！！！
    转移过程是简单的，具体见代码就行。需要注意的是，我们没有加入“至少有一个人不传球”的限制，这个也简单，考虑简单容斥掉就行。用总的方案数减去每个人都要传球的方案数即可。
    最后考虑环怎么办，我们之间枚举第一个位置的 \(0/1\) 状态，然后最后多计算一个位置就行。
点击查看代码
#include
#include
#include
#include
#include
#define ll long long
using namespace std;
const int N=1e5+5;
const int Mod=998244353;
int n;
int a[N];
ll iv2,iv6;
ll f[N][2];
inline ll ksm(ll x,ll y){ll res=1;while(y){if(y&1) res=res*x%Mod;y>>=1;x=x*x%Mod;}return res;
}
inline ll S1(ll x){return x*(x+1)/2%Mod;
}
inline ll S2(ll x){return x*(x+1)%Mod*(2*x+1)%Mod*iv6%Mod;
}
inline ll calc(int w1,int w2){f[1][1]=w1;f[1][0]=w1^1;for(int i=1;i<=n;i++){int v=i%n+1,w=a[i];f[v][0]=(f[i][0]*S1(a[i]-w2)%Mod+f[i][1]*(a[i]+1-w2)%Mod)%Mod;f[v][1]=(f[i][0]*(a[i]*S1(a[i])%Mod-S2(a[i])+Mod)%Mod+f[i][1]*S1(a[i])%Mod)%Mod;}return (w1?f[1][1]:f[1][0]);
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;iv6=ksm(6,Mod-2);for(int i=1;i<=n;i++) cin>>a[i];// cout<