1703: 二进制数
金币值：2
定数：1
时间限制：1.000 s
内存限制：128 M
正确：0
提交：0
正确率：0.00% 命题人：
题目描述
蚌埠是交通枢纽城市，既有铁路大动脉也有沿淮河的水路运输。大宗货物计划在蚌埠装船运往毫州，出发前需要进行全面的检查，这些检查需要委托专业团队进行。为确认团队资质，有时会设计测试题目，要求团队解答。
定义 f(x):N+→N＋为满足以下性质的函数：其中＆为二进制按位与运算。
f(x)=k^2+1 for x=2^k
f(x)=f(y)+f(z) for x=y+z and y&z=0
其中&为二进制位与运算
给定正整数n,求f(x)的前缀和 即 x= [1,n] 的f(x)的和
答案对 998244353取模
输入格式
输入的第1行包含1个整数T，表示数据组
对每组数据，第1行包含1个整数m，表示正整
数n在二进制下的长度。
接下来1行包含1个十六进制整数n
输出格式
对每组数据，输出1行1个整数表示答案
输入样例 复制
3
2
3
16
dead
16
beef输出样例 复制
6
33243107
27134320提示
1<=T<=15
1<=m<=1e5
对于样例第一组 ,f(1)=1 f(2) =2 ,f(3)=f(1)+f(2)=3 故前缀和为 6