CSP 模拟 47
A 玩水
结论题，观察发现 \(a_{i+1,j}=a_{i,j+1}\) 很关键，称满足这样的点 \((i,j)\) 为好点。然后图上画一画发现充要条件就是有两个好点，要么相邻，要么在另一个的严格左上方，证明就是自己手玩一下就知道了。
B AVL 树
不会
C 暴雨
朴素的计算是简单的，处理出前后缀最大值，一个位置的贡献就是 \(\min(pre_i,suf_i)-s_i\)。
容易想到 \(f_{i,j,??,0/1}\) 表示到 \(i\) 选了 \(j\) 次，现在为奇偶数的方案数，但是中间不知道是什么，再想想可以想到中间可以用前缀最大值做状态，但是发现一个问题，只知道前缀最大值并没有什么用，因为不知道后面的情况，所以直接考虑这个最大值是有用的，设 \(f_{i,j,k,0/1}\) 表示到 \(i\)，选了 \(j\) 次，前缀最大值为 \(k\)，现在为奇偶数的方案数，这样算完还是不能知道答案，于是再倒着做一遍，两个 DP 拼接起来就合法了。
乍一看方程状态数是 \(n^2k\) 的，但是由于只能删 \(k\) 个，所以前缀最大值是与 \(k\) 同阶的，这样复杂度就对了。先拿 std::set 和 std::map 之类的预处理出前缀的 \(k\) 个最大值（离散化后的），然后直接暴力 DP 即可。
两遍做完之后，拼接直接暴力枚举乘法原理即可，注意保证两边都小于或小于等于当前值，不能同时小于等于是因为中间有平台会算重。
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define pii std::pair<int,int>
#define eb emplace_back
typedef long long ll;
typedef unsigned long long ull;
std::mt19937 myrand(std::chrono::high_resolution_clock::now().time_since_epoch().count());
inline int R(int n){return myrand()%n+1;}
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=3e4+10,mod=1e9+7;
int n,m,num[N];
ll ans;
struct Node{
int s[N],f[N][30][30][2],rec[N][30],all[N];
__gnu_pbds::gp_hash_table<int,int> mp[N];
std::set<int> se;
inline void sol(){
for(int i=0;i<=n;++i){
for(auto x:se)mp[i].insert({x,++all[i]}),rec[i][all[i]]=x;
if(mp[i].find(s[i])==mp[i].end())mp[i].insert({s[i],++all[i]}),rec[i][all[i]]=s[i];
se.insert(s[i]);if(se.size()>m+1)se.erase(se.begin());
}
f[0][0][1][0]=1;
for(int i=0;i<n;++i)
for(int j=0;j<=m;++j)
for(int k=1;k<=all[i];++k)
for(int pos=0;pos<=1;++pos)
if(f[i][j][k][pos]){
int val=std::max(s[i+1],rec[i][k]),p=pos^(val-s[i+1])&1;
int id=mp[i+1].find(val)->second;
f[i+1][j][id][p]=(f[i+1][j][id][p]+f[i][j][k][pos])%mod;
if(j>=m)continue;
val=rec[i][k];id=mp[i+1].find(val)->second;p=pos^(val&1);
f[i+1][j+1][id][p]=(f[i+1][j+1][id][p]+f[i][j][k][pos])%mod;
}
}
}pre,suf;
signed main(){
freopen("rain.in","r",stdin);freopen("rain.out","w",stdout);
// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
n=read(),m=read();for(int i=1;i<=n;++i)pre.s[i]=num[i]=suf.s[n-i+1]=read();
pre.sol(),suf.sol();
for(int i=1;i<=n;++i)
for(int j=0;j<=m;++j){
int sl=0,sr=0;
for(int k=1;k<=pre.all[i];++k)if(pre.rec[i-1][k]<num[i])sl=(sl+pre.f[i-1][j][k][0])%mod,sr=(sr+pre.f[i-1][j][k][1])%mod;
for(int q=1;q<=suf.all[n-i];++q)if(suf.rec[n-i][q]<=num[i])ans=(ans+1ll*sl*suf.f[n-i][m-j][q][0]+1ll*sr*suf.f[n-i][m-j][q][1])%mod;
}
std::cout<<ans<<'\n';
}
D 置换
不会
E 传统题
确实比较传统和套路，每次枚举拼接连续段可以做到 \(n^3\)，设 \(f_{i,x}\) 表示到 \(i\) 最长连续段小于等于 \(x\) 的方案数，前缀和优化可以 \(n^2\)。
求恰好，自然地想到容斥，设 \(len\) 为连续段长度，\(F(len)\) 为 \(len\) 满足某个条件的方案数，首先答案可以表示为
直接考虑计算后面，考虑枚举连续段的数量 \(j\)，然后就成了经典的组合问题，选出 \(j\) 个数和为 \(n\)，但是这里每个数都有一个上界，转化成统计不合法的，就成了下界，\(F(len<=i)=\sum_{k=0}^{j}(-1)^k{j\choose k}{n-ik-1\choose j-1}\)，现在就成了求 \(\sum_{i=0}^{n-1}\sum_{j=1}^{n}m(m-1)^{j-1}\sum_{k=0}^{j}(-1)^k{j\choose k}{n-ik-1\choose j-1}\)，整理一下式子：
推不动了（生成函数好像还能推），前面两个和式是调和级数的复杂度，很优秀了，根据题解，现在要考虑后面的组合意义，有 \(n-ik\) 个小球，先选出来 \(j\) 个，再从 \(j\) 个中选出来 \(k\) 个，然后从 \(j\) 个中选出一个，除此之外的 \(j-1\) 个小球全部染上 \(m-1\) 种颜色。
这样解释后发现选 \(j\) 个的一步意义不大，消去后就成了从 \(n-ik\) 个小球中选出来 \(k\) 个，再从剩下的小球中选出一个子集，从 \(k\) 个或子集中选出一个特殊的，然后对剩下所有选出来的小球染色。
发现特殊的小球比较关键，有两种情况：
- 特殊的小球在 \(k\) 个中，方案数是 \(k(m-1)^{k-1}m^{n-ik-k}\)，第 \(m\) 种颜色表示是否选这个小球。
- 特殊的小球不在 \(k\) 个中，方案数是 \((m-1)^{k}(n-ik-k)m^{n-ik-k-1}\)。
两种情况加起来，就是最后一个和式：
预处理出次幂，组合数，前面调和计数，后面直接计算，时间复杂度 \(\mathcal{O}(n\log n)\)。
#include<bits/stdc++.h>
#define int long long
#define pii std::pair<int,int>
#define eb emplace_back
typedef long long ll;
typedef unsigned long long ull;
std::mt19937 myrand(std::chrono::high_resolution_clock::now().time_since_epoch().count());
inline int R(int n){return myrand()%n+1;}
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=3e5+10;
int n,m,mod,jc[N],ny[N],inv[N],ans,_1[N],_0[N];
inline void AD(int &x,int y){x=(x+y)%mod;}
inline int qpow(int a,int b){int res=1;for(;b;b>>=1,a=a*a%mod)if(b&1)res=res*a%mod;return res;}
inline int C(int x,int y){if(y>x)return 0;return jc[x]*ny[y]%mod*ny[x-y]%mod;}
inline void init(){
_1[0]=_0[0]=ny[0]=ny[1]=inv[1]=jc[0]=jc[1]=1;for(int i=2;i<=n;++i)inv[i]=(mod-mod/i)*inv[mod%i]%mod,jc[i]=jc[i-1]*i%mod;
ny[n]=qpow(jc[n],mod-2);for(int i=n;i;--i)ny[i-1]=ny[i]*i%mod;for(int i=1;i<=n;++i)_1[i]=_1[i-1]*(m-1)%mod,_0[i]=_0[i-1]*m%mod;
}
signed main(){
// freopen("sequence.in","r",stdin);freopen("sequence.out","w",stdout);
// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
n=read(),m=read(),mod=read();init();
for(int i=0;i<n;++i){
for(int k=0;k*i+k<=n&&k<=n;++k){
int fl=inv[n-i*k]*C(n-i*k,k)%mod;if(k&1)fl*=-1;
int res=0;if(k)res=k*_1[k-1]%mod*_0[n-i*k-k]%mod;
AD(res,_1[k]*_0[n-i*k-k-1]%mod*(n-i*k-k)%mod);
AD(ans,res*fl%mod);
}
}ans=ans*m%mod;
std::cout<<((_0[n]*n%mod-ans)%mod+mod)%mod<<'\n';
}