LOJ3395 「2020-2021 集训队作业」Yet Another Permutation Problem

考虑什么样的排列可以通过 $k$ 次操作达到。不难发现当且仅当排列中存在一个区间，满足区间单增且区间长度 $\ge n - k$ 。由于存在会比较难以统计，可以考虑求出所有极长连续段长度 $\le n - k - 1$ 的排列数量，然后用 $n!$ 减去即可。

考虑枚举 $t$ ，计算所有极长上升段都 $\le t$ 的方案数。考虑一个暴力，先暴力对整个序列分段，令这些段就是极长上升段，然后不难发现限制是段内 $<$ 和段间 $>$ 。这个东西非常难以统计，所以考虑容斥掉 $>$ 符号，于是就会让一些上升段合并成同一个大段，而对大段进行分配就非常简单了，因为大段之间被容斥成了无限制，所以这些大段内的分配方案就是 $\frac{n!}{\prod a_i!}$ ，容斥系数就是 $-1$ 的每个大段内小段的个数减 $1$ 次方的积。由于统计大段会比统计小段轻松得多，所以可以转而枚举大段的划分，对于同一个大段划分方案，它的贡献就是 $\frac{n!}{\prod a_i!}$ 乘上每个大段的每种拆成小段的方案的容斥系数的和的积。

不妨称每个大段的每种拆成小段的方案的容斥系数的和为这个大段的容斥系数，可以发现这个系数只和大段长度有关。设 $h(a)$ 表示长度为 $a$ 的大段的容斥系数乘上 $-1$ ，因为原本的容斥系数是段间的个数，如果乘上就可以变成段的个数，会更方便统计。考虑转移，可以枚举最后一个小段的长度，由于小段的长度不能超过 $t$ ，所以是

h(a) = \sum_{i = a - t}^{a - 1} -h(i)

显然， $h(0) = 1,h(1) = -1$ ，然后发现 $h(2) = h(3) = \cdots = h(t) = 0 , h(t + 1) = 1 , h(t + 2) = -1 \dots$ ，也就是说这东西是循环的，同时只在每 $t+1$ 个位置中有两个位置有值。

于是回到这之前。现在我们知道了如何计算一个大段的容斥系数，于是可以对整个序列进行一次 $dp$ 来划分成若干大段。可以设 $dp[i]$ 表示已经划分了 $1 \dots i$ ，所有划分方案的 $\frac{n!}{\prod a_i!} \prod h(a_i)$ 的和。会发现转移的时候，每 $t+1$ 个只有 $2$ 个位置有值，所以做这个 $dp$ 的复杂度是 $O(\frac{n^2}{t})$ ，总复杂度为 $\sum_t \frac{n^2}{t} = O(n^2\ln n)$ ，可以通过这个题。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 200006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , P;
int A[MAXN];
int dp[MAXN] , as[MAXN];
int J[MAXN] , iJ[MAXN];

int Pow( int x , int a ) {
	int ret = 1;
	while( a ) {
		if( a & 1 ) ret = ret * 1ll * x % P;
		x = x * 1ll * x % P , a >>= 1;
	}
	return ret;
}

void solve() {
	cin >> n >> P;
	J[0] = iJ[0] = 1;
	rep( i , 1 , n ) J[i] = J[i - 1] * 1ll * i % P , iJ[i] = Pow( J[i] , P - 2 );
	rep( k , 0 , n - 1 ) {
		dp[0] = J[n];
		rep( i , 1 , n ) dp[i] = 0;
		rep( i , 1 , n ) {
			dp[i] = ( dp[i] + dp[i - 1] ) % P;
			for( int l = k + 1 ; l <= i ; l += ( k + 1 ) ) {
				dp[i] = ( dp[i] + P - dp[i - l] * 1ll * iJ[l] % P ) % P;
				if( i >= l + 1 ) dp[i] = ( dp[i] + dp[i - l - 1] * 1ll * iJ[l + 1] ) % P;
			}
		}
		as[n - k - 1] = ( J[n] + P - dp[n] ) % P;
	}
	rep( i , 0 , n - 1 ) printf("%d\n",as[i]);
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}