#P3791. 普通数学题

    ID: 4513 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: 7 上传者: 标签>洛谷原创O2优化枚举进制前缀和洛谷月赛

普通数学题

题目背景

一天 zzq 没有题可以出了。于是他随便写了一个式子,求i=0nj=0mixorjxorx\sum_{i=0}^n \sum_{j=0}^m i \operatorname{xor}j\operatorname{xor}x,其中 xor\operatorname{xor} 表示异或。

zzy 一看,这不是水题吗,就随便加了一个函数:i=0nj=0md(ixorjxorx)\sum_{i=0}^n \sum_{j=0}^m d(i \operatorname{xor}j\operatorname{xor}x),其中 xor\operatorname{xor} 表示异或,d(x)d(x) 表示 xx 的约数个数。注意 d(0)=0d(0)=0

现在 zzq 不会做了,只好写了一个暴力造了数据,然后把这道题丢给了你。

题目描述

输入三个数 n,m,xn,m,x,要求计算 i=0nj=0md(ixorjxorx)\sum_{i=0}^n \sum_{j=0}^m d(i \operatorname{xor}j\operatorname{xor}x),其中 xor\operatorname{xor} 表示二进制下的异或,d(x)d(x) 表示 xx 的约数个数。

由于答案比较大,要求输出答案模 998244353 998244353 后的结果。

输入格式

一行三个数 n,m,xn,m,x

输出格式

输出答案模 998244353 998244353 后的结果。

输入数据 1

0 2 233

输出数据 1

14

输入数据 2

123 234 345

输出数据 2

205761

提示

对于 20%20\% 的数据,n,m,x2000n,m,x \leq 2000

对于 50%50\% 的数据,n,m,x106n,m,x \leq 10^6

对于 80%80\% 的数据,n,m,x108n,m,x \leq 10^8

对于 100%100\% 的数据,1n,m,x10101 \leq n,m,x \leq 10^{10}