#P14139. 行动路线

    ID: 13345 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>组合数学多项式与生成函数FFT图论动态规划CF2400多项式生成函数

行动路线

省选模拟赛 B

题目描述

在平面直角坐标系的 (i,0)(i,0) 上有 aia_i 个不同的人,0≤i≤n0\le i\le n。 对于每个 0≤j≤n0\le j\le n,从 (0,0),…,(j,0)(0,0),\ldots,(j,0) 上的所有人中选择一个人, 让他每步向右或向上移动一个单位,直到到达 (j,j)(j,j)。

记 bjb_j 为选择人及规划路径的方案数。选择的人不同或路径不同均视为不同方案。 当路径长度为0时,也有一种空路径。求

⨁j=0n(bj mod 998244353),\bigoplus_{j=0}^{n}(b_j\bmod998244353),

其中 ⊕\oplus 为按位异或。

输入格式

一行两个整数 n,seedn,seed。用下方生成器调用A.init(seed),然后依次调用 n+1n+1 次A.XP()生成 a0,…,ana_0,\ldots,a_n。

生成器中的全部状态运算使用64位无符号整数;加法先按 2642^{64} 回绕, 之后再对998244353取模。

输出格式

输出一行一个整数,表示上述异或值。

数据范围

0≤n≤1060\le n\le10^6,0≤seed<2640\le seed<2^{64}。

随机数生成器

下载 gen.cpp

#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

参考附件

原题资料(本页约定为准)