#P12735. 回报

    ID: 11252 Type: RemoteJudge 1000ms 512MiB Tried: 0 Accepted: 0 Difficulty: 6 Uploaded By: Tags>2025洛谷原创组合数学容斥原理快速数论变换 NTT洛谷月赛

回报

题目背景

在我看来,得到太多的人明明是我,反倒是我该思考怎么回报才对。
——浅村悠太

题目描述

悠太需要帮沙季找到合适的学习用音乐。

他找到了一个包含 nn 首音乐的专辑,其中的音乐编号为从 11nn,播放每首音乐均需要 11 分钟。沙季有 A 和 B 两门需要学的课程,每次学习 A 和 B 分别需要花 a,ba,b 分钟。为了更好地帮助她,悠太打算将音乐的播放顺序重新排列。具体地,他要选择一个长为 nn 的排列 p1,,pnp_1,\dots,p_n,使得其中存在两个长度分别为 a,ba,b 的循环 A,BA,B,且 AA 中的任意一个元素小于 BB 中的任意一个元素。

排列中的一个长为 kk 的循环 CC 是一个由不同整数组成的序列 c1,,ckc_1,\dots,c_k,满足 1c1n1\le c_1\le nci+1=pci,i=1,,k1c_{i+1}=p_{c_i},i=1,\dots,k-1,且 pck=c1p_{c_k}=c_1

悠太想要求出有多少满足要求的排列 pp。由于答案可能很大,你只需要告诉他答案对 998244353998244353 取模的结果。

输入格式

输入一行三个整数表示序列长度 nna,ba,b

输出格式

输出一行一个整数,表示满足要求的排列的数量取模 998244353998244353 的结果。

4 2 1

3

678 12 34

951781526

1987 654 321

27905503

1000000 13 20

912829543

提示

样例 1 解释

满足要求的排列有 (2,1,3,4),(3,2,1,4),(1,3,2,4)(2,1,3,4),(3,2,1,4),(1,3,2,4),共 33 个。

数据范围与限制

本题采用捆绑测试,各 Subtask 的限制与分值如下。

Subtask No. nn\le 特殊性质 分值 依赖子任务
11 1010 77
22 700700 1010 11
33 2020 1,21,2
44 20002000 1010
55 3030 1,2,3,41,2,3,4
66 10610^6 2020 1,2,41,2,4
77 33 1,2,3,4,5,61,2,3,4,5,6

特殊性质:min(a,b)=1\min(a,b)=1

对于所有数据,1n1061\le n\le10^61a,b<a+bn1\le a,b<a+b\le n