#P9621. 与巨

    ID: 6235 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 6 上传者: 标签>CF2100提高2-adic 赋值等差数列求和同余的加减乘运算模逆元

与巨

题目描述

定义无穷序列 ff:f1=1,fn=fn−1×2+1\displaystyle f_1=1,f_n=f_{n-1}\times 2+1。

定义函数 G(x)=min⁡fi≥xfi\displaystyle G(x)=\min_{f_i\ge x}f_i。

定义 $\displaystyle g_{c,0}=0,g_{c,i}=\max(g_{c,i-1},[((i\times c)\And G(i))=i]\times i)$。

求 ∑i=0ngc,i mod 998244353\displaystyle \sum^n_{i=0} g_{c,i} \bmod 998244353。

输入格式

第一行输入一个整数 TT,表示数据组数。

每组测试用例输入一行包含两个整数 n,cn,c。

其中 nn 以二进制形式表示,且 nn 不含有前导 00。

输出格式

对于每组测试用例输出一行一个整数表示答案。

样例

5
1001 1
11111 1
101010111101 8999
10100101111010101 799
10010010 233
45
496
2835797
707482963
9940

数据范围

测试点 数据约束
1∼41\sim 4 ∣n∣≤20|n|\le 20 ,c≤109c\le 10^9
5∼85\sim 8 ∣n∣≤30|n|\le 30 ,c≤50c\le 50
9∼129\sim 12 ∣n∣≤2×105|n|\le 2\times 10^5 ,c≤109c\le 10^9
13∼2013\sim 20 无特殊约束

对于全部数据,1≤T≤101\le T\le 10,1≤∣n∣≤1071\le |n|\le 10^7,∑∣n∣≤107\sum |n|\le 10^7,1≤c≤10181\le c\le 10^{18}。