Loj#6670.「XXOI 2019」一个希望直接实现

Loj#6670.「XXOI 2019」一个希望直接实现

题解

题意

定义一个$1 - n$的排列$P$的$k$划分为：把$P$从左到右每$k$个划分成一组， 如果有剩下的，则剩下的一共成一组。

定义$P$的$k$最小取样为：把它的$k$划分$P'$中，每组只保留这一组中最小的数。

那么就会得到$\frac{n}{k}$个数，如果它们从左到右构成一个递增的等差数列， 则称其为「可以达成愿望」的。

如果$P$的$k$最小取样是「可以达成愿望」的，则$f(P, k) = 1$， 否则$f(P, k) = 0$。

给定$n$，定义$P_n$为$1 - n$的全排列的集合， 求：

$$\sum_{p \in P_n } \sum_{k | n}f(P, k)$$

对$998244353$取模。

解法

首先假设块长为$k$， 不难发现，满足条件的等差数列的首项一定是$1$，公差$d \in [1, k]$，然后我们只需要去枚举约数，去求对应的$k$， 然后枚举公差$d$，去确定对应的方案数，确定公差后对应的等差数列也就确定为：

$$1,1 + d, 1 + 2d , \cdots ,1 + (k - 1)d$$

然后考虑最后一个块，会有多出来的能填的数，我们就可以将其填在前面，接下来考虑等差数列每一项之间的数，这之间的数肯定不能填在后面的块内，倒着填数的时候只能填在这个块和这个块之前，也就是说每次填数会少$k - 1$个数，多$d - 1$个数，也构成了一个等差数列。比如$n = 9, k = 3$时， 对应的方案数为$A_2^2 \times A_3^2 \times A_4^2 \times 3 ^ 3$，由于我们只考虑了除了等差数列之外的数，所以必须最后乘上每个块内的最小值的排列方案数。

code >folded

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 3e5 + 10;
const int mod = 998244353;

int n;

int fac[N], ifac[N];

int qpow(int a, int b)
{
    int t = 1;
    while(b != 0)
    {
        if(b & 1)t = t * a % mod;
        a = a * a % mod; b >>= 1;
    }
    return t;
}

int inv(int x)
{
    return qpow(x, mod - 2);
}

int A(int n, int m)
{
    return fac[n] % mod * ifac[n - m] % mod;
}

int calc(int x)
{
    int sum = 0, len = n / x;
    for(int d = 1; d <= x; d++)
    {
        int res = 1;
        for(int i = 0, j = x - 1; i < len; i++, j += x - d)
            res = res * A(j, x - 1) % mod * x % mod;
        sum = (sum + res) % mod;
    }
    return sum;
}

signed main()
{
    int sum = 0;
    cin >> n;
    int ans = 0; fac[0] = ifac[0] = 1;
    for(int i = 1; i <= n; i++)
        fac[i] = fac[i - 1] * i % mod;
    for(int i = 1; i <= n; i++)
        ifac[i] = inv(fac[i]);
    for(int i = 1; i < n; i++)
    {
        if(n % i)continue;
        ans = (ans + calc(i)) % mod;
    }
    ans = (ans + fac[n] + mod) % mod;
    cout << ans;
    return 0;
}