C - Multiple Sequences¶

题意¶

整数 $N$ , $M$ が与えられます。長さ $N$ の整数列 $A$ であって、以下の条件を満たすものの数を答えてください。

$1\le A_i\le M$ ( $i=1,2,\ldots,N$ )
$A_{i+1}$ は $A_i$ の倍数 ( $i=1,2,\ldots,N−1$ )

ただし、答えは非常に大きくなる場合があるので、 $998244353$ で割った余りを答えてください。

解析¶

我们只需要枚举 $A_N$ 的值，然后根据算术基本定理将 $A_N$ 分解为

$A_N=\prod_{i=1}^cp_i^{k_i}$

之后，我们需要分配这些质因子的位置。每个不同的质因子之间的分配都是独立的，我们只需要对每个质因子单独考虑。

我们要将 $k_i$ 个 $p_i$ 分配到 $N$ 个位置。如果 $A_i$ 被分配到了 $C$ 个 $p_i$ ，则使 $A_i=p_i^CA_{i-1}$ 。显然，分配方案数为 $\binom{N+k_i-1}{N-1}$ 。

于是， $A_N$ 为 $x=\prod\limits_{i=1}^cp_i^{k_i}$ 的方案数为 $\prod\limits_{i=1}^c\binom{N+k_i-1}{N-1}$ 。枚举 $A_N$ 的值即可，总复杂度为 $O(N+M\sqrt M)$ 。

实现¶

#include <bits/stdc++.h>

typedef long long int ll;
const int maxn = 2e5 + 19, mod = 998244353;//1004535809;

int fact[maxn << 1], ifact[maxn << 1];
void exgcd(int a, int b, int &x, int &y){
    if(!b) return (void)(x = 1, y = 0);
    exgcd(b, a % b, y, x), y -= a / b * x;
}
void init(int n){
    fact[0] = 1;
    for(int i = 1; i <= n; ++i) fact[i] = (ll)fact[i - 1] * i % mod;
    exgcd(fact[n], mod, ifact[n], ifact[n - 1]);
    for(int i = n - 1; i >= 0; --i) ifact[i] = (ll)ifact[i + 1] * (i + 1) % mod;
}
inline int binom(int n, int m){
    return (ll)fact[n] * ifact[n - m] % mod * ifact[m] % mod;
}

int n, m, ans;

int main(){
    std::scanf("%d%d", &n, &m), init(n + m - 1);
    for(int i = 1; i <= m; ++i){
        int x = i, res = 1;
        for(int j = 2; j * j <= x; ++j)
            if(x % j == 0){
                int cnt = 0;
                while(x % j == 0)
                    x /= j, ++cnt;
                res = (ll)res * binom(cnt + n - 1, n - 1) % mod;
            }
        if(x != 1) res = (ll)res * n % mod;
        ans = (ans + res) % mod;
    }
    std::printf("%d\n", ans);
}

来源¶

AtCoder Regular Contest 116 C - Multiple Sequences

C - Multiple Sequences¶

题意¶

解析¶

实现¶

来源¶

评论