关于组合数的奇偶性的近10条评论(全部评论)
Lucas ？ ‎MistyEye 2016-12-19 17:08 6楼
wa这么多次全部死在溢出上，简直了 confoo 2016-12-18 22:53 5楼
O(1)大法好 _Itachi 2016-12-18 14:25 4楼
回复 @Drench : 好吧，失误了= = 试图卡按位分解失败...... AntiLeaf 2016-12-18 10:46 3楼
题面好像打错了一个地方，$m_i$递推式的第二项根据样例看是$m_{i-1}$不是$n_{i-1}$。 Drench 2016-12-18 08:53 2楼
%%%%%%%%% 沉迷学习的假的Keller 2016-12-18 08:12 1楼

2573. [HZOI 2016]组合数的奇偶性

★ 输入文件：comb.in 输出文件：comb.out 简单对比
时间限制：1 s 内存限制：64 MiB

有$T$组询问，每次给出两个非负整数$n,m$，请你判断组合数$C_n^m$的奇偶性。

为了避免I/O量过大，每组询问的$n$和$m$不再由输入文件给出，而采用以下方式生成：

$n_i = A * n_{i-1}^2 + B * n_{i-1} + C \mod M$

$m_i = D * m_{i-1}^2 + E * m_{i-1} + F \mod M$

其中，参数$A,B,C,n_0,D,E,F,m_0,M$由输入文件给出，你需要用上述递推式求得$(n_1,m_1)$~$(n_T,m_T)$的值。

输出的格式也有变化，具体见输出格式。

认为$C_0^0=1$，$C_n^m=0(m>n)$。

一行10个非负整数$T,A,B,C,n_0,D,E,F,m_0,M$，意义如上所述。

为了在减小输出量的同时保证你答案的正确性，我们需要你输出三个数：所有结果为奇数的询问编号之和，所有结果为奇数的询问编号的异或和，所有结果为奇数的询问编号平方的异或和。询问的编号为1~$T$。

单独一行输出三个数，表示我们要求你提供的三个数。

10 9 8 7 6 5 4 3 2 11

20 14 92

对于20%的数据，T<=1000，M<=1000。

对于50%的数据，T<=200000，M<=5000000。

对于100%的数据，T<=5000000，0<M<$2^{31}$，保证给出的$A,B,C,n_0,D,E,F,m_0$均<M。

请注意不要制造太大的常数。

水题

似乎是经典问题