#P18438. Yet Another Subsequence Problem

Yet Another Subsequence Problem

Yet Another Subsequence Problem

对于任意两个正整数 a,ba,b,使用下面的 C++ 代码定义函数:

std::string gen_string(int64_t a, int64_t b) {
    std::string res;
    int64_t ia = 0, ib = 0;
    while (ia + ib < a + b) {
        if ((__int128)ia * b <= (__int128)ib * a) {
            res += '0';
            ia++;
        } else {
            res += '1';
            ib++;
        }
    }
    return res;
}

循环结束时,ia 等于 aa,ib 等于 bb。因此函数返回一个长度为 a+ba+b、恰含 aa 个 0 和 bb 个 1 的字符串。例如,gen_string(4, 10) = 01110110111011。

给定参数 A,BA,B,求 gen_string(A, B) 的本质不同的子序列数量,答案对 998244353998244353 取模。

序列 xx 是字符串 yy 的子序列,当且仅当可以从 yy 中删除若干个字符(可以不删,也可以全部删除)得到 xx。因此空子序列也要计数;相同的结果字符串只计算一次。

输入格式

第一行一个整数 TT(1≤T≤1001\le T\le100),表示独立测试用例数。

接下来 TT 行,每行两个整数 A,BA,B(1≤A,B≤10181\le A,B\le10^{18})。

输出格式

每个测试用例输出一行,表示 gen_string(A, B) 的本质不同子序列数量对 998244353998244353 取模后的结果。

原样例 1

6
1 1
3 5
4 7
8 20
4 10
27 21
4
70
264
196417
609
667131122

原样例 2

18
5 9
23 30
820 483
5739 9232
86494 55350
606 13336
2768848 1124639
47995594 66053082
1069395 7177
7801842511 4390103762
47882886553 82678306054
193410894 6189355686
51594638 19992922190
59 110
422735115778072 658356435030265
9125338158530266 5328357177709583
60743352262021049 95595862538791630
629312141725417942 999581828389011547
988
220693002
133474535
202371605
778839228
282057418
935955056
943144752
409056617
627433544
578769776
917438628
24364208
109943645
352575425
68058533
402004723
894026897