排列[jzoj6709]

发表于 分类于

题意

problem

题解

做多了FFT，这题似乎感觉还是挺简单滴~。

显然容斥一下，设 $g_n$ 表示恰好 $i$ 个的答案，设 $f_n$ 表示至少 $i$ 个的答案。

那么有：$f_i=\sum_{j=i}^ng_j\binom{j}{i}$。

二项式反演一下：$g_i=\sum_{j=i}^n(-1)^{j-i}\binom{j}{i}f_j$。

这个是一个卷积形式，求完 $f_i$ 后一个卷积就好了。

下面来看如何求 $f_i$。

我们建一个二分图，$X_i,Y_j$ 连边当且仅当 $|i-j|=m$。我们选一条边 $(i,j)$ 表示令 $P_i=j$。

对于 $f_i$ 而言，我们需要在这个二分图中找到 $i$ 条边的方案数，最后乘一个随意乱连的方案，即 $(n-i)!$。

那么对于二分图中的一条链，假设长度为 $k$，你需要选 $j$ 条边，那么方案数就为 $h_j=\binom{k-j}{j}$。

然后把这个 $h$ 写成生成函数的形式，那么在二分图中找到 $i$ 条边的方案数相当于就是将所有的链的 $h$ 乘起来后的第 $i$ 项。

因为这些链的 $h$ 的次数的和是 $n$，因此这个也可以随便做做就好了。比如写个最低级的多项式快速幂。

时间复杂度 $O(n\log n)$。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
const ll mod=998244353;
inline ll Add(ll x,ll y){x+=y; return (x<mod)?x:x-mod;}
inline ll Dec(ll x,ll y){x-=y; return (x<0)?x+mod:x;}
inline ll Mul(ll x,ll y){return x*y%mod;}
inline ll Pow(ll x,ll y)
{
	y%=(mod-1);ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1) ans=ans*x%mod;
	return ans;
}
#define Poly vector<ll>
const int M=1<<19;
const int N=1e5+5;
ll W[M];
int R[M];
inline void nttinit()
{
	ll w;
	for(int i=1;i<M;i<<=1)
	{
		W[i]=1; w=Pow(3,(mod-1)/(i<<1));
		fo(j,1,i-1) W[i+j]=W[i+j-1]*w%mod;
	}
}
inline void ntt(ll *a,int n,int opt)
{
	ff(i,0,n)
	{
		R[i]=(R[i>>1]>>1)|((i&1)*(n>>1));
		if(i<R[i]) swap(a[i],a[R[i]]);
	}
	ll w;
	for(int i=1;i<n;i<<=1)
		for(int j=0;j<n;j+=(i<<1))
			for(int k=0;k<i;k++)
				w=W[i+k]*a[i+j+k]%mod,
				a[i+j+k]=Dec(a[j+k],w),
				a[j+k]=Add(a[j+k],w);
	if(opt==1) return;
	reverse(a+1,a+n);
	w=Pow(n,mod-2);
	ff(i,0,n) a[i]=w*a[i]%mod;
}
inline void ntt(Poly &A,int n,int t) {ntt(&A[0],n,t);}
inline Poly operator *(Poly A,Poly B)
{
	int n=A.size(),m=B.size(),k=n+m-1,len=1;
	for(;len<k;len<<=1);
	A.resize(len); B.resize(len);
	ntt(A,len,1); ntt(B,len,1);
	ff(i,0,len) A[i]=Mul(A[i],B[i]);
	ntt(A,len,-1);
	A.resize(k);
	return A;
}
inline Poly operator ^(Poly A,int k)
{
	Poly B; B.resize(0); B.push_back(1);
	for(;k;k>>=1,A=A*A) if(k&1) B=B*A;
	return B;
}
ll fac[N],inv[N];
inline void facinit(int n)
{
	fac[0]=1;
	fo(i,1,n) fac[i]=fac[i-1]*i%mod;
	inv[n]=Pow(fac[n],mod-2);
	fd(i,n,1) inv[i-1]=inv[i]*i%mod;
}
inline ll C(int n,int m)
{
	if(n<0||m<0||n<m) return 0;
	return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
Poly A,B,F,G,H;
int k,n,m,len;
int main()
{
	FO(perm);
	nttinit();
	cin>>n>>m;
	facinit(n+1);
	k=n%m; len=n/m+1;
	A.resize(len/2+1);
	fo(i,0,len/2) A[i]=C(len-i,i);
	A=A^(k<<1);
	k=m-n%m; len--;
	B.resize(len/2+1);
	fo(i,0,len/2) B[i]=C(len-i,i);
	B=B^(k<<1);
	F=A*B;
	fo(i,0,n) F[i]=Mul(Mul(F[i],fac[n-i]),fac[i]);
	G.resize(n+1);
	fo(i,0,n) G[n-i]=Pow(mod-1,i)*inv[i]%mod;
	H=G*F;
	fo(i,0,n) printf("%lld\n",H[i+n]*inv[i]%mod);
	return 0;
}