洛谷 P4916 题解

admin 2021-07-24 AM 150℃ 0条

题目链接

分析

感谢 zhs 大佬的讲解。

假定最后一个珠子是白色。现在在不考虑旋转的情况下求出答案。记这个答案为 $S(n,m)$。

首先将 $n-m$ 个白色珠子排成一排。在每一个白珠子前面插入一些黑珠子。

发现不能有连续 超过 $k$ 个黑珠子的限制不好考虑。容斥。

设 $f_i$ 为至少有 $i$ 个区间(指两个白珠子之间)里插入了超过 $k$ 个黑珠子的方案数。

则 $S(n,m)=\sum_{i=0}^{n-m}(-1)^i\times f_i$。

$f_i$ 可以用隔板法计算。先强制在 $i$ 个区间里面插入 $k+1$ 个黑珠子,然后其它黑珠子随便放。

即 $f_i=\binom{n-m}{i}\times \binom{n-i(k+1)-1}{n-m-1}$。

现在考虑循环同构的限制。

我们发现,如果按照上述方式计算,一个黑白珠子的排列方式会被重复计算其最小循环节次。

设 $g_i$ 为循环节个数为 $i$ 的倍数的排列方案数,$h_i$ 为最小循环节个数为 $i$ 的排列方案数。

首先,$g_i>0$ 当且仅当 $i|m$ 且 $i|n-m$。也就是 $i|gcd(n,m)$。

然后考虑如何计算 $g_i$。

因为 $i|gcd(n,m)$,所以满足最小循环节长度为 $i$ 的因数的排列方案一定满足 $i$ 也是其循环节。

只需要考虑一个循环节内部的小环。故 $g_i=S(\dfrac{n}{i},\dfrac{m}{i})$。

最后考虑如何计算 $h_i$。

有 $g_i=\sum\limits_{i|d}h(d)$。

莫比乌斯反演得 $h(i)=\sum\limits_{i|d}\mu(\dfrac{i}{d})g(d)$。

答案为 $\sum\limits_{d|gcd(n,m)}\dfrac{h(d)\times d}{n-m}$。

模数是质数,预处理逆元、阶乘、阶乘的逆元、莫比乌斯函数即可。

时间复杂度不知道怎么算,但是跑得飞快。

解决

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 1e5 + 5, MOD = 998244353;
int n, m, k, d;
int inv[N], invfac[N], fac[N], mu[N], prime[N], cnt, g[N];
bool isPrime[N];

void prework()
{
    memset(isPrime, true, sizeof(isPrime));
    isPrime[1] = false, mu[1] = 1;
    for (int i = 1; i <= n; i++)
    {
        if (isPrime[i])
        {
            mu[i] = -1;
            prime[++cnt] = i;
        }
        for (int j = 1; j <= cnt && i <= n / prime[j]; j++)
        {
            isPrime[i * prime[j]] = false;
            if (i % prime[j])
                mu[i * prime[j]] = -mu[i];
            else
            {
                mu[i * prime[j]] = 0;
                break;
            }
        }
    }
    inv[0] = inv[1] = invfac[0] = invfac[1] = fac[0] = fac[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        inv[i] = 1LL * inv[MOD % i] * (MOD - MOD / i) % MOD;
        invfac[i] = 1LL * invfac[i - 1] * inv[i] % MOD;
        fac[i] = 1LL * fac[i - 1] * i % MOD;
    }
}

int C(int m, int n)
{
    if (m < 0 || n < 0 || m < n)
        return 0;
    return 1LL * fac[m] * invfac[n] % MOD * invfac[m - n] % MOD;
}

int S(int n, int m)
{
    int ans = 0;
    for (int i = 0; i <= m / (k + 1); i++)
    {
        int res = 1LL * C(n - m, i) * C(n - i * (k + 1) - 1, n - m - 1) % MOD;
        if (i & 1)
            ans = (ans - res + MOD) % MOD;
        else
            ans = (ans + res) % MOD;
    }
    return ans;
}

int H(int x)
{
    int ans = 0;
    for (int i = x, j = 1; i <= d; i += x, j++)
        if (mu[j] == 1)
            ans = (ans + g[i]) % MOD;
        else if (mu[j] == -1)
            ans = (ans - g[i] + MOD) % MOD;
    return ans;
}

int gcd(int x, int y)
{
    int r = x % y;
    while (r)
        x = y, y = r, r = x % y;
    return y;
}

int main()
{
    cin >> n >> m >> k;
    if (m == 0)
    {
        puts("1");
        return 0;
    }
    prework();
    d = gcd(n, m);
    for (int i = 1; i <= d; i++)
        if (d % i == 0)
            g[i] = S(n / i, m / i);
    int ans = 0;
    // for (int i = 1; i <= 3; i++) printf("H(%d) = %d\n", i, H(i));
    for (int i = 1; i <= d; i++)
        if (d % i == 0)
            ans = (ans + 1LL * H(i) * i) % MOD;
    cout << 1LL * ans * inv[n - m] % MOD << endl;
    return 0;
}
标签: none

非特殊说明,本博所有文章均为博主原创。

评论啦~