1225 : 又一个子序列问题
Time Limit: 1 Sec Memory Limit: 256 MB Submitted: 1 Solved: 1Description
对于任意两个正整数 \(a\) 和 \(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\) 将等于 \(a\)，\(ib\) 将等于 \(b\)，因此该函数会返回一个长度为 \(a+b\) 的 \(01\) 字符串，其中恰好有 \(a\) 个 \(0\) 和 \(b\) 个 \(1\)。
例如，\(gen\_string(4,10)=01110110111011\)。
给定参数 \(A, B\)，你需要计算 \(gen\_string(A, B)\) 的本质不同的子序列的数量，并将答案对 \(998244353\) 取模后输出。
注意：序列 \(a\) 是字符串 \(b\) 的子序列，当且仅当 \(a\) 可以通过删除 \(b\) 中的若干（可能为零或全部）元素得到。
Input
第一行包含一个整数 \(T\ (1\le T\le 100)\)，表示测试用例的数量。
接下来的 \(T\) 行，每一行包含两个整数 \(A\) 和 \(B\) (\(1\le A,B \le 10^{18}\))，意义如题面所述。
Output
对于每个测试用例，输出 \(gen\_string(A, B)\) 的不同子序列的数量，对 \(998244353\) 取模后输出。
Sample
6 1 1 3 5 4 7 8 20 4 10 27 21 ##CASE## 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
4 70 264 196417 609 667131122 ##CASE## 988 220693002 133474535 202371605 778839228 282057418 935955056 943144752 409056617 627433544 578769776 917438628 24364208 109943645 352575425 68058533 402004723 894026897
Hint
Author
SYSU