CCPC郑州站 笨蛋题 II

yr说他们队这题A了就Au了，可惜

离散数学太无聊了，课上想的。xd半节课就切了，我想了两节课才会，做法好像不太一样。

我做计数推式子的时候总是不太流畅，感觉还是不太专注导致的。

Sol

考虑一个具体的前缀最大值方案 \(s = \array{a_1,a_2,...,a_{|s|}}\)，要如何计算有多少个排列的前缀最大值方案是 \(s\)

对于 \(s\)，特别地，我们钦定 \(a_0 = 0\)，\(a_{|s|} = n\)，我们现在考虑非前缀最大值的数要怎么放，我们尝试从后往前计算。

具体地，依次从后往前考虑 \(1\leq i \leq |s|\)，\((a_{i-1},a_i)\) 里面的每一个数，\((a_{i-1},a_i)\) 里面的数只能够放到 \(a_i\) 后面，放在 \(a_i\) 后面也不会影响到后面的前缀最大值。

那么对于 \((a_{i-1},a_i)\) 它的贡献系数就是 ：

\[\binom{n-a_{i-1}-1}{a_i-a_{i-1}-1}(a_i-a_{i-1}-1)! = \frac{(n-a_{i-1}-1)!}{(n-a_i)!} \]

那么所有 \(i\) 的系数乘起来就是关于这个方案的排列个数:

\[\frac{(n-1)!}{\Pi_{i=1}^{|s|-1}(n-a_i)} \]

现在我们计算这个方案出现的期望次数，也就是算这个方案出现的概率，我们记上面计算出的关于 \(s\) 的方案数为 \(f(s)\)：

\[1-(\frac{n!-f(s)}{n!})^k = 1-(1-\frac{f(s)}{n!})^k = 1-(1-\frac{1}{\Pi_{i=0}^{|s|-1}(n-a_i)})^k \]

因为除以 \((n-1)!\) 后变成了 \(\frac{1}{n}\)，前文有定义 \(a_0 = 0\)，所以相当于从 \(i=0\) 开始计算了。

所以答案就是:

\[\sum_{s} 1-(1-\frac{1}{\Pi_{i=0}^{|s|-1}(n-a_i)})^k = 2^{n-1}-\sum_{s} (1-\frac{1}{\Pi_{i=0}^{|s|-1}(n-a_i)})^k \]

现在好像没什么思路了，因为式子没有可以继续化简的地方，此时的形式也不能够让我们直接处理，因为那个 \(k\) 次方，所以考虑对于后面那部分二项式展开：

\[\begin{align} \sum_{s} (1-\frac{1}{\Pi_{i=0}^{|s|-1}(n-a_i)})^k \\ = \sum_{i=0}^{k}\binom{k}{i}\sum_{s}(-\frac{1}{\Pi_{j=0}^{|s|-1}(n-a_j)})^i \\ = \sum_{i=0}^{k}\binom{k}{i}(-1)^i\sum_{s}\frac{1}{\Pi_{j=0}^{|s|-1}(n-a_j)^i} \end{align} \]

对于最后一个和式那里，容易发现这个只和 \(i\) 有关，并且对于同一个 \(i\) ，这个式子的结果容易用递推直接求出来，具体的，设 \(g(i,j)\) 表示 \(i\) 次方，当前 \(s\) 的最后一个元素是 \(j\)（前缀最大值是递增的）,上述式子的值是多少，简单dp即可，下面是代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define db double
const ll N = 5005,mod = 998244353;
ll n,k,C[N][N],pw2[N],f[N][N],g[N][N],s[N][N],h[N]; 
ll qpow(ll a,ll p){ll res = 1;for(;p;p>>=1,a=a*a%mod) if(p&1) res = res*a%mod;return res;
}
void solve(){cin >> n >> k;pw2[0] = 1;for(int i=1;i<=n;i++) pw2[i] = pw2[i-1]*2%mod;C[0][0] = 1;for(int i=1;i<=k;i++){C[i][0] = 1;for(int j=1;j<=i;j++){C[i][j] = C[i-1][j]+C[i-1][j-1];if(C[i][j] >= mod) C[i][j] -= mod;}}for(int i=1;i<=n;i++){f[i][0] = 1;ll inv = qpow(i,mod-2);for(int j=1;j<=k;j++){f[i][j] = f[i][j-1]*inv%mod;}}for(int i=0;i<=k;i++){if(i) h[i] = g[i][0] = f[n][i];else h[i] = g[i][0] = 1;for(int j=1;j<n;j++){g[i][j] = h[i]*f[n-j][i]%mod;h[i] = (h[i]+g[i][j])%mod; }}ll ans = 0;for(int i=0;i<=k;i++){if(i&1) {ans = ans+(mod-C[k][i]*h[i]%mod);ans %= mod;}else{ans = ans+C[k][i]*h[i]%mod;ans %= mod;}}ans = pw2[n-1]-ans;ans = (ans%mod+mod)%mod;cout << ans << '\n';
}
int main(){cin.tie(0),cout.tie(0);ios::sync_with_stdio(0);int T = 1;
//	cin >> T;while(T--) solve();return 0;
}

容易发现这题本质上就是一道计算题，熟能生巧。