Description

给定 $ n, k $，请求出长度为 $ n $ 的逆序对数恰好为 $ k $ 的排列的个数。答案对 $ 10 ^ 9 + 7 $ 取模。

对于一个长度为 $ n $ 的排列 $ p $，其逆序对数即满足 $ i < j $ 且 $ p_i > p_j $ 的二元组 $ (i, j) $ 的数量。

一行两个整数 $ n, k $。

一行，表示答案。

对于 $ 20% $ 的数据，$ n, k \leq 20 $；

对于 $ 40% $ 的数据，$ n, k \leq 100 $；

对于 $ 60% $ 的数据，$ n, k \leq 5000 $；

对于 $ 100% $ 的数据，$ 1 \leq n, k \leq 100000, 1 \leq k \leq \binom{n}{2} $。

Solution

可以想到，对于一个排列 $p$ ，假设 $s_i$ 表示以 $i$ 为右端点的逆序对个数，那么可以看出一个 $s_{1,2,...,n}$ 对应一个唯一的 $p$ ，而一个 $s_{1,2,...,n}$ 合法当且仅当 $\forall i,s_i\le i-1$。

可以想到我们可以容斥，即枚举哪些点 $s_i$ 越界了。那么，我们也就只需要求出

\[\prod_{i=1}^{n}(1-x^i)
\]

的前面 $k$ 项。

这个时候我们就有两种办法，一种是用多项式，取 $\ln$ ，然后用 $\ln(1-x)=\sum_{j=1}^{\infty} -\frac{x^j}{j}$ $\Theta(k\log k)$ 直接多项式 $\ln,\exp$ 算出来，考场上我就写的这个，不过原题要写任意模数 NTT，估计不是很好写，而且常数很大，可以拿头过。

还有另外一种 $\Theta(k\sqrt k)$ 做法。你发现选出一个 $\{1,2,...,n\}$ 的集合还有另外一种选法，即假设你现在有一个递减序列，你每次有两种选择：

整体加 $1$
整体加 $1$ 并在后面增加一个 $1$

那么，我们就可以进行 dp 了，因为考虑到我们最多使用 $\sqrt k$ 次操作 $2$，所以，我们可以设 $f_{i,j}$ 表示在经过 $i$ 此操作 $2$ 后数字总和为 $j$ 的方案数。

可以得到转移式：

\[f_{i,j}=f_{i,j-i}+f_{i-1,j-i}-f_{i-1,j-n-1}
\]

Code

#include <bits/stdc++.h>

using namespace std;

#define Int register int

#define mod 1000000007

#define MAXN 200005

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}

template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}

template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}

template <typename T> inline void chkmax (T &a,T b){a = max (a,b);}

int n,k,upp = 2e5,fac[MAXN],ifac[MAXN],f[505][MAXN];

int mul (int a,int b){return 1ll * a * b % mod;}

int dec (int a,int b){return a >= b ? a - b : a + mod - b;}

int add (int a,int b){return a + b >= mod ? a + b - mod : a + b;}

int qkpow (int a,int b){

	int res = 1;for (;b;b >>= 1,a = mul (a,a)) if (b & 1) res = mul (res,a);

	return res;

}

void Sub (int &a,int b){a = dec (a,b);}

void Add (int &a,int b){a = add (a,b);}

int binom (int a,int b){return a >= b ? mul (fac[a],mul (ifac[b],ifac[a - b])) : 0;}

int F[MAXN];

signed main(){

	read (n,k);int up = 500;

	fac[0] = 1;for (Int i = 1;i <= upp;++ i) fac[i] = mul (fac[i - 1],i);

	ifac[upp] = qkpow (fac[upp],mod - 2);for (Int i = upp;i;-- i) ifac[i - 1] = mul (ifac[i],i);

	f[0][0] = 1;

	for (Int i = 1;i <= up;++ i)

		for (Int j = 0;j <= k;++ j){

			if (j >= i) Add (f[i][j],add (f[i][j - i],f[i - 1][j - i]));

			if (j >= n + 1) Sub (f[i][j],f[i - 1][j - n - 1]);

		 }

	for (Int S = 0;S <= k;++ S)

		for (Int i = 0;i <= up;++ i)

			if (i & 1) Sub (F[S],f[i][S]);

			else Add (F[S],f[i][S]);

	int ans = 0;

	for (Int S = 0;S <= k;++ S) Add (ans,mul (F[S],binom (k - S + n - 1,n - 1)));

	write (ans),putchar ('\n');

	return 0;

}

巴特西

题解「2017 山东一轮集训 Day7」逆序对

Description

Solution

Code

最新文章

热门文章

巴特西

题解 「2017 山东一轮集训 Day7」逆序对

Description

Solution

Code

最新文章

热门文章

题解「2017 山东一轮集训 Day7」逆序对