luogu#P7433. [THUPC2017] 老司机

    ID: 11435 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 7 上传者: 标签>2017快速傅里叶变换,FFT快速数论变换 NTT

[THUPC2017] 老司机

题目描述

四环路上行人稀,常有车神较高低。

如今车道依旧在,不见当年老司机。

B 君心情不好的时候,喜欢去四环路上飙车。看着窗外飞驰而过的景色,B 君想到了过去的 R 君和 G 君;想到了现在的 YJQ 和 FLZ;想到了宇宙之浩渺,时空之无限;也想到了这道题。

输入 n,X,Y,Zn,X,Y,Z,保证 XX22 的整数次幂,YY33 的整数次幂,ZZ55 的整数次幂,同时 1n1000,1X×Y×Z20001\le n\le 1000,1\le X\times Y\times Z\le2000

输入四个长度为 nn 的数组 {ai},{bi},{ci},{ri}\{a_i\},\{b_i\},\{c_i\},\{r_i\}0ai,bi,ci,ri1090\le a_i,b_i,c_i,r_i\le10^9)。

对于 (u,v,w)(u,v,w) 求有多少组解 {xi},{yi},{zi}\{x_i\},\{y_i\},\{z_i\}

满足对于所有的 ii,有 $a_i\le x_i,b_i\le y_i,c_i\le z_i,r_i\ge x_i-a_i+y_i-b_i+z_i-c_i$。

并且

(i=1nxi)modX=u(\sum_{i=1}^nx_i)\bmod X=u (i=1nyi)modY=v(\sum_{i=1}^ny_i)\bmod Y=v (i=1nzi)modZ=w(\sum_{i=1}^nz_i)\bmod Z=w

设解的个数为 F(u,v,w)F(u,v,w)

输出

$$\operatorname*{xor}_{0\le u< X,0\le v<Y,0\le w<Z}((uYZ+vZ+w)\times(F(u,v,w)\bmod466560001)) $$

输入格式

输入第一行 n,X,Y,Zn,X,Y,Z

接下来 nn 行,第 ii 行四个整数 ai,bi,ci,ria_i,b_i,c_i,r_i

输出格式

一行一个整数表示答案。

3 2 3 1
0 0 0 1
0 0 0 2
0 0 0 3
573
3 2 3 5
0 0 0 1
0 0 0 2
0 0 0 3
253

提示

版权信息

来自 THUPC(THU Programming Contest,清华大学程序设计竞赛)2017。