三道排列组合好题
或许是人品不错，最近两天接连刷到三道排列组合相关的题。在此作简单整理。
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解法。在此不做讨论。
- 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个多小时……
- 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; }
近期评论