1703: 2024AHCPC - 二进制数
金币值：2
定数：1
时间限制：1.000 s
内存限制：128 M
正确：1
提交：1
正确率：100.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 \le T \le 15$ $1 \le m \le 1e5$
对于样例第一组 ,$f(1)=1 f(2) =2 ,f(3)=f(1)+f(2)=3$ 故前缀和为 $6$.