#P18724. Disks and Gems
Disks and Gems
Disks and Gems
珠宝匠 Monocarp 接到一份奇怪的订单,需要制作一套镶有宝石的金属圆盘。每个圆盘的材质是铜、银、金三者之一;圆盘被分成 n 个扇区,按顺时针方向编号为 1 到 n。宝石有 k 种类型,每个扇区至多镶一颗宝石;没有宝石的扇区称为空扇区。
当且仅当两个圆盘每个相同编号的扇区都同时为空,或镶有相同类型的宝石,它们的花纹相同。只有材质也相同,两个圆盘才相同。扇区编号固定,不把旋转视为同一花纹。
制作每个圆盘时,先任意选择一种材质,得到 n 个空扇区。然后依次处理类型 1,2,…,k:每个类型恰镶两颗宝石。第一颗可以放在任意空扇区;第二颗必须放在从第一颗出发顺时针遇到的下一个空扇区。每次已放置的宝石都保留。处理完后,恰有 n−2k 个空扇区。
例如 n=5,k=2:先选银质圆盘;把类型1放在4号,接着放在顺时针下个空位5号;再把类型2放在3号,下个空位是1号,因为4、5号已有宝石,于是放在1号。
Monocarp 要组成满足以下条件的集合:其中任意两个圆盘的花纹均不同(这也保证两个圆盘不同),并且集合中圆盘的数量尽可能多。求他能组成的不同集合数,模 998244353 输出。两个集合相同,当且仅当每个集合的每个圆盘都能在另一集合中找到相同圆盘。
输入格式
第一行一个整数 t(1≤t≤300000)。之后每组一行两个整数 n,k,满足 2≤n≤900000000,1≤k≤⌊n/2⌋。
输出格式
每组输出一个整数,为不同最大集合的数量模 998244353。
完整原样例
8
4 1
4 2
5 2
10 2
10 4
10 5
1337 42
888888888 8
81
81
14348907
412733925
572390210
572390210
359416572
358909282
原样例说明
第一组最多能制作4种花纹:[0,0,1,1]、[1,0,0,1]、[0,1,1,0]、[1,1,0,0]。0表示空扇区,1表示类型1。每种花纹可以任选三种材质之一,所以答案为 3^4=81。
花纹[1,0,1,0]不可能出现:若先选1号,下个空位是2号,得到[1,1,0,0];若先选3号,下个空位是4号,得到[0,0,1,1]。