三道排列组合好题

或许是人品不错，最近两天接连刷到三道排列组合相关的题。在此作简单整理。

AtCoder ABC226 F – Score of Permutations

题意参见原题面。

很自然地想到，对于一个排列$P = (p_1, p_2, \dots, p_n)$，有$n$条$i \rightarrow p_i$的连边。因为排列中正整数$1, 2, \dots, n$恰好出现仅有一次，所以等价于每个点有且仅有一条出边、一条入边的图。容易发现这个图由若干个有向环构成（包括自环——即$p_i = i$的情况）。例如排列$P = (1, 3, 4, 2)$代表由$1 \rightarrow 1$和$2 \rightarrow 3 \rightarrow 4 \rightarrow 2$两个环组成的图。

根据题意，一个排列$P$的分数，就是其构成的图中各个环长度的最小公倍数。容易发现，一条长度确定的环，它对分数的贡献与其包含的点的编号等无关。所以我们考虑怎么分配这些环的长度。易得所有这些环的长度之和为$n$，则这个问题可以转化成有多少种互不相同的方法，可以将自然数$n$分成若干个自然数之和。

假定我们已经求出一种分配方法，$n = a_1 k_1 + a_2 k_2 + \dots + a_t k_t$，其中$a_i$表示某个自然数，$k_i$表示其出现次数。则由排列组合的知识可得，一共有$$\prod\limits_{i=1}^{t} \prod\limits_{j=1}^{k_i} \binom{n-(\sum_{q = 1}^{i-1}a_q k_q)-j a_i}{a_i}$$种将点分配进各个环的方式。又因为我们重复统计了相同的$k_i!$长度为$a_i$的环（例如，对于$a_i = 2, k_i = 2$，分配$4$个点，$\{1,3\}\{2, 4\}$的分配和$\{2,4\}\{1,3\}$的分配被上面的式子算成了两种方式，但它们对应到排列中完全相同），所以答案还要除以$$\prod\limits_{i=1}^{t}k_t!$$。又发现，在每一个长度为$a_i$的环内部，假设我们钦定环的一个起点，那么剩下的点将有$(a_i-1)!$种环内排列方式，也就是本质不同的环数。所以方案数还要再乘上$$\prod\limits_{i=1}^{t}((a_i-1)!)^{k_i}$$。设上面式子的计算结果为$S$，我们求出$\mathrm{lcm}(a_1, a_2, \dots, a_t)$，则这种分配方法将对答案产生$S \times (\mathrm{lcm}\{a\})^K$的贡献。

例如我们考虑$n=7$时的一种拆分$\{1,3,3\}$，则有$\binom{7}{3} \times \binom{7-3}{3} \times \binom{7-3*2}{1} = 140$种分配方法，其中对于长为$3$的环，重复计算了$2!$次，对于长度为$1$的环，重复计算了$1!$次；各个环内部的不同顺序由乘法原理可得有$((3-1)!)^2 \times ((1-1)!)^1 = 4$种，故$S=140/(2! \times 1!)*4=280$，每种排列的分数为$\mathrm{lcm}\{1, 3, 3\} = 3$，故将对答案产生$280 \times 3^K$的贡献。

我们利用剪枝优化的搜索求出$n$的所有不同拆分方法。实际计算得到，$50$共有约$2\times 10^5$种拆分方式，再加上快速幂的时间，可以通过本题。

另有一种非常高效的DP解法。在此不做讨论。

Submission #27195443

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
#include <bits/stdc++.h>
using namespace std;

const int N = 64, P = 998244353;
int n, k, g[N], ans, fact[N], f;

int fast_pow (int x, int y) {
	int res = 1 % P;
	for (; y; y >>= 1) {
		if ((y & 1)) res = 1ll * res * x % P;
		x = 1ll * x * x % P;
	}
	return res;
}
int gcd (int a, int b) { return a % b ? gcd (b, a % b) : b; }
int C (int n, int m) { return 1ll * fact[n] * fast_pow (1ll * fact[m] * fact[n - m] % P, P - 2) % P; }
void terminate (int len) {
	int q = n, res = 1, freq, now, lcm;
	for (int i = 1; i <= len; ++i)
		res = 1ll * res * C (q, g[i]) % P * fact[g[i] - 1] % P, q -= g[i];
	now = g[1], freq = 1, g[len + 1] = -1, lcm = g[1];
	for (int i = 2; i <= len + 1; ++i)
		if (now != g[i]) {
			res = 1ll * res * fast_pow (fact[freq], P - 2) % P;
			freq = 1, now = g[i];
			lcm = lcm * g[i] / gcd (lcm, g[i]);
		} else ++freq;
	ans = (1ll * ans + 1ll * fast_pow (lcm, k) * res % P) % P;
	f += res;
}

void calc (int sum, int ima, int pos) {
	if (sum == n) {
		terminate (pos);
		return;
	}
	for (int i = ima; i <= min (n, n - sum); ++i) {
		g[pos + 1] = i;
		calc (sum + i, i, pos + 1);
	}
}

int main () {
	/* ABC226 F - Score of Permutations 吴秋实 */
	fact[0] = 1;
	for (int i = 1; i <= 52; ++i)
		fact[i] = 1ll * fact[i - 1] * i % P;
	scanf ("%d%d", &n, &k);
	calc (0, 1, 0);
	
	printf ("%d", ans);

	return 0;
}

NOIP模拟 20211112 T1 – 谜之阶乘

给定正整数$n$，你需要求出所有使得$\dfrac{a!}{b!}=n$成立的$a,b$。$n \leq 10^{18}$。

天河一号都受不了暴力枚举的复杂度。所以我们考虑聪明一点的方法。

我们发现，$20! > 10^{18} > 19!$，所以无论怎样，若是$n = \prod_{i=a}^{a+k-1} i$，那么必然有$k \leq 19$。现在，我们钦定一个$k$，则考虑$n= \dfrac{a!}{(a-k)!}$，它显然具有关于$a$的单调性。所以我们枚举$k$，然后二分$a$的值，最后检查计算出的答案是否和$n$相等即可。

同时需要注意，由于$n!$增长极快，二分的上限不能随意设置。详见代码。

时间复杂度$\mathrm{O}(19 \times T \log n)$，$T$为测试数据组数。非常优秀，可以把std吊起来打。

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
#include <bits/stdc++.h>
using namespace std;

int T, cnt; long long n, x, l, mid, r;
long long lmt[24] = {0, (long long)1e18 + 10, (long long)1e9 + 10, (long long)1e6 + 10, 31650,
	4000, 1010, 380, 190, 110, 70, 50, 40, 32, 27, 24, 22, 21, 20, 20};
struct ans {
	long long a, b;
	friend bool operator < (ans x, ans y) { return x.a < y.a; }
} g[24];

long long calc (long long x, int k) {
	long long res = 1;
	for (long long i = x; i > x - k; --i)
		res *= i;
	return res;
}

void bi_search (int k) {
	l = k + 1, r = lmt[k];
	while (l < r) {
		mid = (l + r + 1) >> 1;
		if (calc (mid, k) > n) r = mid - 1;
		else l = mid;
	}
	if (calc (l, k) == n)
		g[++cnt].a = l, g[cnt].b = l - k;
}

int main () {
	/* MOCK NOIP 20211112 吴秋实 */
scanf ("%d", &T);
while (T--) {
	scanf ("%lld", &n);
	if (n == 1) {
		puts ("-1");
		continue;
	}
	cnt = 0;
	for (int i = 1; i <= 19; ++i)
		bi_search (i);
	printf ("%d\n", cnt);
	sort (g + 1, g + cnt + 1);
	for (int i = 1; i <= cnt; ++i)
		printf ("%lld %lld\n", g[i].a, g[i].b);
}

	return 0;
}

AtCoder ABC 227 G – Divisors of Binomial Coefficient

计算二项式系数$\dbinom{n}{k}$的因数个数。$n \leq 10^{12}, k \leq \min(n, 10^6)$。答案对$998244353$取余。

这个式子可以化成$\dfrac{n!}{k!(n-k)!}$，也就是$\dfrac{1}{k!} \prod\limits_{i=n-k+1}^{n} i$。

我们当然不可能真的把这$2k$个数的因数个数$\mathrm{O}(k\sqrt{n})$地求出来再加减，但由算术基本定理可得，对于一个确定的质因子$p$，其在$n!$中的个数就是$1~n$中每个数包含的$p$的个数的和。更进一步，$1$到$n$中，$p$的倍数，也就是至少包含一个质因子$p$的数的个数显然有$\lfloor n/p \rfloor$个。同理，包含至少两个该质因子，即$p^2$的倍数的数有$\lfloor n/p^2 \rfloor$个。不过，对于每个这样的数，其中有一个质因子已经在$\lfloor n/p \rfloor$中统计过了，所以我们累加上$\lfloor n/p^2 \rfloor$即可。

又因为除了质数外，$(n-k, n]$中每一个数的质因子不可能超过$\sqrt{n} \leq 10^6$，所以我们使用线性筛求出$1$到$\max(\sqrt{n}, k)$的质数，对于一个质数$p$，其在$\prod\limits_{i=n-k+1}^{n} i$中的质因子个数就是$$\sum\limits_{i=1}^{\lfloor \log_{p} n \rfloor}(\lfloor {\dfrac{n}{p^i}} \rfloor – \lfloor {\dfrac{n-k}{p^i}} \rfloor)$$。再考虑$\dfrac{1}{k!}$，同理可得$k!$包含的质因子$p$的个数是$$\sum\limits_{i=1}^{\lfloor \log_{p} k \rfloor}\lfloor {\dfrac{k}{p^i}} \rfloor$$，所以将$p$的质因子计数$cnt[p]$减去上式即可。

同时，为了筛出$(n-k, n]$中剩余的大于$\sqrt{n}$的质因数，我们记录该区间中每一个数当前剩余的因数积$f[i]$，对于每一个$p$，我们将$gp \in (n-k, n]$的因数积$f[gp]$不断除以该质因数$p[i]$，直至无法整除为止。最后检查$f[i]$，发现其不是$1$，说明其包含且恰好包含一个某个大于$\sqrt{n}$质因数。可以证明，最后筛选出的这些质因数在整个式子中仅出现一次。

由算术基本定理推得，最终答案就是$\prod\limits_p (cnt[p] + 1)$。

由于每个质因数都会遍历一遍值域$(n-k, n]$然后作除法，故复杂度是$\mathrm{O}(t \ln (n – k)), t = \max (k, \sqrt{n})$。

TMD线性筛写错了——暴力手搓数据调了2个多小时……

Submission #27243869

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10, P = 998244353;
int p[N], fac[N], pcnt;
long long cnt[N], haji;
long long fuck[N];
long long n, k, g, q, ans;

int main () {
	/*  */
	scanf ("%lld%lld", &n, &k);
	if (k > n - k) k = n - k;
	g = max ((long long)sqrt (n), k);
	// 计算n! / (n - k)!相关的质因子。 
	for (long long i = n - k + 1; i <= n; ++i)
		fuck[i - (n - k)] = i;
	for (int i = 2; i <= g; ++i) {
		if (!fac[i]) {
			fac[i] = p[++pcnt] = i;
			q = i;
			while (q <= n) {
				cnt[pcnt] += n / q - (n - k) / q - k / q;
				q = q * i;
			}
			haji = (n - k + 1) % i ? i - ((n - k + 1) % i) + n - k + 1 : n - k + 1; 
			for (; haji <= n; haji += i)
				while (fuck[haji - (n - k)] % i == 0)
					fuck[haji - (n - k)] /= i;
		}
		for (int j = 1; j <= pcnt; ++j) {
			if (i * p[j] > g || fac[i] < p[j]) break;
			fac[i * p[j]] = p[j];
		}
	}
	for (long long i = n - k + 1; i <= n; ++i)
		if (fuck[i - (n - k)] != 1) cnt[++pcnt] = 1, p[pcnt] = fuck[i - (n - k)];
	ans = cnt[1] + 1;
	for (int i = 2; i <= pcnt; ++i)
		ans = 1ll * ans * (cnt[i] + 1) % P;
	printf ("%d\n", ans);

	return 0;
}