題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 CF2183E LCM is Legendary Counting Master

rating: 2065

Problem Statement

題目簡述

給定長度為 nn 的序列 aa 和正整數 mm，序列元素範圍為 [0,m][0, m]。需將序列中的 00 替換為 [1,m][1, m] 之間的整數，使得序列滿足以下條件：

  1. 嚴格遞增：a1<a2<…<ana_1 < a_2 < \ldots < a_n。
  2. LCM 不等式：∑i=1n−11lcm⁡(ai,ai+1)+1lcm⁡(an,a1)≥1\sum_{i=1}^{n-1} \dfrac{1}{\operatorname{lcm}(a_i, a_{i+1})} + {\color{red}{\dfrac{1}{\operatorname{lcm}(a_n, a_1)}}} \ge 1。

求填補 00 的合法方案數，模 998244353998244353。

Constraints

約束條件

  • 2≤n≤m≤30002 \le n \le m \le 3000
  • 0≤ai≤m0 \le a_i \le m

思路：數論轉化 + DP

本題的關鍵在於分析 LCM 不等式的結構，將其簡化為可計數的約束條件。

1. 核心數學推導

利用 lcm⁡(x,y)=x⋅ygcd⁡(x,y)\operatorname{lcm}(x, y) = \dfrac{x \cdot y}{\gcd(x, y)}，原不等式可以改寫為：

∑i=1n−1gcd⁡(ai,ai+1)aiai+1+gcd⁡(an,a1)ana1≥1\sum_{i=1}^{n-1} \dfrac{\gcd(a_i, a_{i+1})}{a_i a_{i+1}} + {\color{red}\dfrac{\gcd(a_n, a_1)}{a_n a_1}} \ge 1

關鍵不等式

對於任意 x<yx < y，恆有 gcd⁡(x,y)≤y−x\gcd(x, y) \le y - x。

證明

設 g=gcd⁡(x,y)g = \gcd(x, y)，則 g∣xg \mid x 且 g∣yg \mid y，故 g∣(y−x)g \mid (y - x)。
又因 y>xy > x，所以 g≤y−xg \le y - x。

將此性質代入，對前 n−1n-1 項套用上界：

gcd⁡(ai,ai+1)aiai+1≤ai+1−aiaiai+1=1ai−1ai+1\dfrac{\gcd(a_i, a_{i+1})}{a_i a_{i+1}} \le \dfrac{a_{i+1} - a_i}{a_i a_{i+1}} = \dfrac{1}{a_i} - \dfrac{1}{a_{i+1}}

對於最後一項（循環回 a1a_1），因 a1a_1 為序列最小值，有 gcd⁡(an,a1)≤a1\gcd(a_n, a_1) \le a_1，故：

gcd⁡(an,a1)ana1≤a1ana1=1an{\color{red}\dfrac{\gcd(a_n, a_1)}{a_n a_1}} \le \dfrac{a_1}{a_n a_1} = \dfrac{1}{a_n}

將所有項相加，相鄰項抵消後可得：

Sum≤(1a1−1a2)+(1a2−1a3)+⋯+(1an−1−1an)+1an=1a1\text{Sum} \le \left(\dfrac{1}{a_1} - \dfrac{1}{a_2}\right) + \left(\dfrac{1}{a_2} - \dfrac{1}{a_3}\right) + \cdots + \left(\dfrac{1}{a_{n-1}} - \dfrac{1}{a_n}\right) + \dfrac{1}{a_n} = \dfrac{1}{a_1}

必要條件

題目要求 Sum≥1\text{Sum} \ge 1，而上界為 1a1≤1\dfrac{1}{a_1} \le 1。因此：

  1. a1=1a_1 = 1（使上界恰好等於 11）
  2. 所有不等式必須取等號（否則總和將嚴格小於 11）

2. 等號成立條件

要使等號成立，對 i=1,…,n−1i = 1, \ldots, n-1 的相鄰元素 (ai,ai+1)(a_i, a_{i+1}) 必須滿足：

gcd⁡(ai,ai+1)=ai+1−ai\gcd(a_i, a_{i+1}) = a_{i+1} - a_i

設 d=ai+1−aid = a_{i+1} - a_i，則 gcd⁡(ai,ai+d)=gcd⁡(ai,d)=d\gcd(a_i, a_i + d) = \gcd(a_i, d) = d，即 dd 必須整除 aia_i。

循環邊的等號條件

對於 (an,a1)(a_n, a_1)，等號條件為 gcd⁡(an,a1)=a1\gcd(a_n, a_1) = a_1。當 a1=1a_1 = 1 時，gcd⁡(an,1)=1=a1\gcd(a_n, 1) = 1 = a_1 自動成立。

問題轉化

計數滿足以下條件的序列數：

  • a1=1a_1 = 1，ai<ai+1≤ma_i < a_{i+1} \le m
  • 對所有 ii，相鄰差 d=ai+1−aid = a_{i+1} - a_i 必須是 aia_i 的因數
  • 原序列中非 00 的位置必須匹配指定值

3. 動態規劃

根據轉化後的條件設計 DP，使用滾動陣列優化空間：

項目 說明
狀態 f[v]f[v] = 當前位置數值為 vv 的方案數（滾動掉位置維度）
初始 f[1]=1f[1] = 1（因為 a1a_1 必須為 11）；若輸入 a1∉{0,1}a_1 \notin \{0, 1\} 則直接無解
轉移 枚舉當前值 vv 的所有因數 dd，令 nv=v+dnv = v + d。若 nv≤mnv \le m 且符合限制則 f′[nv]←f′[nv]+f[v]f'[nv] \gets f'[nv] + f[v]
限制 若 ai≠0a_i \ne 0（該位置已固定），則只有 nv=ainv = a_i 時才能轉移
答案 最終 ∑vf[v]\sum_{v} f[v] 即為所有合法序列數
實作細節

預處理 1∼m1 \sim m 每個數的所有因數，轉移時直接枚舉。

複雜度分析

  • 時間複雜度：O(n⋅mlog⁡m)\mathcal{O}(n \cdot m \log m)
    • 1∼m1 \sim m 的因數總數約為 O(mlog⁡m)O(m \log m)，故處理一層 DP 的複雜度為 O(mlog⁡m)O(m \log m)。
    • 因數表預處理為一次性成本 O(mlog⁡m)O(m \log m)。
  • 空間複雜度：O(mlog⁡m)\mathcal{O}(m \log m)
    • 預處理因數表需要 O(mlog⁡m)O(m \log m) 的空間。
    • DP 陣列或雜湊表需要 O(m)O(m) 的空間。

Code

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
from collections import defaultdict

MOD = 998244353

MAX_M = 3005
divs = [[] for _ in range(MAX_M)]
for i in range(1, MAX_M):
    for j in range(i, MAX_M, i):
        divs[j].append(i)

def solve():
    n, m = map(int, input().split())
    A = list(map(int, input().split()))
    assert len(A) == n

    if A[0] not in [0, 1]:
        print(0)
        return

    # f[i][v] 表示第 i 個數值為 v 的方案數，滾動掉 i 的維度
    f = defaultdict(int)
    f[1] = 1
    for i in range(1, n):
        nf = defaultdict(int)
        for v in f.keys():
            for d in divs[v]:
                if (nv := v + d) > m:
                    break
                if A[i] == 0 or nv == A[i]:
                    nf[nv] = (nf[nv] + f[v]) % MOD
        f = nf

    print(sum(f.values()) % MOD)

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()

寫在最後

PROMPT

masterpiece, best quality, high quality, good quality, 32K UHD, colorful, official art, illustration, in the style of fashion photography, dynamic, dynamic force picture, (Visual impact:1.2), impactful picture, extreme aesthetic, A shot with tension, sharp focus, The Ninth Art, depth of field, cinematic lighting, light particles, lens flare, movie perspective, (Tyndall Effect:1.4), light particles, light, shadow, scenery, temperate atmosphere, (artist:pigeon666:0.83), (Yomu:0.4), (remsrar:0.45), (quasarcake:0.3),

1girl, solo, Nijika Ijichi (ijichi nijika, bocchi the rock), brown eyes, blonde hair, long hair, very long hair, bangs, side ponytail, school uniform, white shirt, pleated skirt, long sleeves, bow, ahoge, sidelocks, outdoors, collared shirt, bowtie, black skirt, bag, red bow, red bowtie,

holding umbrella, transparent umbrella, rain, raining, night, wet street, puddle, reflection, glowing vending machine, backlighting, neon lights, urban scenery, wide shot, landscape, horizontal, looking at viewer, blush