题解 | #Stack#_牛客博客

题意

令 $f(p)$ 为对排列 $p$ 跑单调栈后剩下的元素个数, 求所有长度为 $n$ 的排列 $P$ 的 $f(P)$ ^3 之和

solution

考虑递推, 令 $f ( n, i )$ 为长度为 $n$ 的所有排列中 $f(p)$ = $i$ 的个数我们的答案就是 $S(n)=\sum_{i=1}^{n} f(n,i)*i^3$

因为 $n+1$ 一定在长度为 $n+1$ 的栈中,且 $n-1$ 前的数一定无贡献故考虑选一些数放到 $n+1$ 后 , n+1 前的所有数可任意排列则可知

$f(n+1,i) = \sum_{j=i}^{n}C_{n}^{j}*(n-j)!*f(j,i-1)$

即

$f(n+1,i)=\sum_{j=i}^{n}(n!/j!)*f(j,i-1)$

$f(n+1,i) = \sum_{j=i}^{n-1}(n!/j!)*f(j,i-1)+f(n,i-1)$ ----(1)

$f(n,i) = \sum_{j=i}^{n-1}((n-1)!/j!)*f(j,i-1)$

$n*f(n,i) = \sum_{j=i}^{n-1}(n!/j!)*f(j,i-1)$ --------------------------(2)

由(1)(2)得

$f(n+1,i)=n*f(n,i)+f(n,i-1)$

故 $S(n+1)=\sum_{i=1}^{n+1} f(n+1,i)*i^3=n*\sum_{i=1}^{n+1} f(n,i)*i^3+\sum_{i=0}^{n} f(n,i)*(i+1)^3$

把 (i+1)^3分解

$S(n+1)= (n+1)*\sum_{i=1}^{n} f(n,i)*i^3 + 3*\sum_{i=1}^{n} f(n,i)*i^2 +3*\sum_{i=1}^{n} f(n,i)*i +\sum_{i=1}^{n} f(n,i)$

而 $\sum_{i=1}^{n} f(n,i)$ 其实就是 $n$ 排列 (即总方案数)

接下来我们只需要想想如何 $O(1)$ 转移

$S_2(n)=\sum_{i=1}^{n} f(n,i)*i^2$

$S_1(n)=\sum_{i=1}^{n} f(n,i)*i$

重复上面的步骤可以知道

$S_1(n+1)$

$=n*\sum_{i=1}^{n} f(n,i)*i+\sum_{i=1}^{n} f(n,i)*(i+1)$

$=(n+1)S_1(n)+n!$

$S_2(n+1)$

$=n*\sum_{i=1}^{n} f(n,i)*i^2+\sum_{i=1}^{n} f(n,i)*(i+1)^2$

$=(n+1)S_2(n)+2*S_1(n)+n!$

由此我们得出了递推式

$S(n)=n*S(n-1)+3*S _2(n-1)+3S_1(n-1)+(n-1)!$

$S_2(n)=n*S _2(n-1)+2S_1(n-1)+(n-1)!$

$S_1(n)=n*S_1(n-1)+(n-1)!$

且 $S(0)=S_1(0)=S_2(0)=0$ ;

预处理所有 $S(n)$ 即可

AC代码:

#include<bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <assert.h>
#include <numeric>
#include <iomanip>
#include <vector>
#include <array>
#include <cmath>
#include <map>
#include <set>
#include<queue>

#ifdef LOCAL
#include "debug.h"
#else
#pragma GCC optmize(2)
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") //// avx / SSE ////
#define Preproce()
#define Endproce()
#define Debug(...)
#endif
#define llng long long
#define int long long

using namespace std;
const int MAX=5e5+9;
const int mod=998244353,inv2=499122177;
int ji[MAX],g[MAX],h[MAX],s[MAX];
void pre(){
    ji[0]=1;
    for(int i=1;i<=5e5;i++){
        ji[i]=ji[i-1]*i;
        ji[i]%=mod;
        h[i]=i*h[i-1]+ji[i-1];
        h[i]%=mod;
        g[i]=i*g[i-1]+2*h[i-1]+ji[i-1];
        g[i]%=mod;
        s[i]=i*(s[i-1])+3*g[i-1]+3*h[i-1]+ji[i-1];
        s[i]%=mod;
    }
}

void solve(){
    int n;
    cin>>n;
    cout<<s[n]<<"\n";
    //for(int i=1;i<=100;i++){
        //cout<<ji[i]<<" "<<h[i]<<" "<<g[i]<<" "<<s[i]<<"\n";
    //}
}
signed main(){
	Preproce();

    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    pre();
    int t1=1;
    cin>>t1;
    while(t1--)
    solve();

    cout.flush();

	Endproce();

    return 0;
}