#P14139. 行动路线
行动路线
省选模拟赛 B
题目描述
在平面直角坐标系的 上有 个不同的人,。 对于每个 ,从 上的所有人中选择一个人, 让他每步向右或向上移动一个单位,直到到达 。
记 为选择人及规划路径的方案数。选择的人不同或路径不同均视为不同方案。 当路径长度为0时,也有一种空路径。求
其中 为按位异或。
输入格式
一行两个整数 。用下方生成器调用A.init(seed),然后依次调用 次A.XP()生成 。
生成器中的全部状态运算使用64位无符号整数;加法先按 回绕, 之后再对998244353取模。
输出格式
输出一行一个整数,表示上述异或值。
数据范围
,。
随机数生成器
#include <cstdint>
using ull = unsigned long long;
struct R{
ull s[2];
inline void init(ull seed){s[0]=seed;s[1]=s[0] ^ 0x7263d9bd8409f526; };
inline ull XP() {
ull s0 = s[0];
ull s1 = s[1];
ull result = s0 + s1;
s1 ^= s0;
s[0] = ((s0<<55) | (s0>>9)) ^ s1 ^ (s1<<14);
s[1] = (s1<<36) | (s1>>28);
return result%998244353;
}
}A;
样例
0 0
920621912