A6871. 「SDOI2016」储能表
编程题
省选/NOI-
知识点
题目描述
有一个 $n$ 行 $m$ 列的表格，行从 $0$ 到 $n - 1$ 编号，列从 $0$ 到 $m - 1$ 编号。
每个格子都储存着能量。最初，第 $i$ 行第 $j$ 列的格子储存着 $ (i \mathbin{\text{xor}} j) $ 点能量。所以，整个表格储存的总能量是，
$$ \sum\limits_{i = 0} ^ {n - 1} \sum\limits_{j = 0} ^ {m - 1} (i \mathbin{\text{xor}} j) $$
随着时间的推移，格子中的能量会渐渐减少。一个时间单位，每个格子中的能量都会减少 $ 1 $。显然，一个格子的能量减少到 $ 0 $ 之后就不会再减少了。
也就是说，$ k $ 个时间单位后，整个表格储存的总能量是，
$$ \sum\limits_{i = 0} ^ {n - 1} \sum\limits_{j = 0} ^ {m - 1} \max((i \mathbin{\text{xor}} j) - k, 0) $$
给出一个表格，求 $k$ 个时间单位后它储存的总能量。
由于总能量可能较大，输出时对 $p$ 取模。
每个格子都储存着能量。最初，第 $i$ 行第 $j$ 列的格子储存着 $ (i \mathbin{\text{xor}} j) $ 点能量。所以，整个表格储存的总能量是，
$$ \sum\limits_{i = 0} ^ {n - 1} \sum\limits_{j = 0} ^ {m - 1} (i \mathbin{\text{xor}} j) $$
随着时间的推移，格子中的能量会渐渐减少。一个时间单位，每个格子中的能量都会减少 $ 1 $。显然，一个格子的能量减少到 $ 0 $ 之后就不会再减少了。
也就是说，$ k $ 个时间单位后，整个表格储存的总能量是，
$$ \sum\limits_{i = 0} ^ {n - 1} \sum\limits_{j = 0} ^ {m - 1} \max((i \mathbin{\text{xor}} j) - k, 0) $$
给出一个表格，求 $k$ 个时间单位后它储存的总能量。
由于总能量可能较大，输出时对 $p$ 取模。
输入格式
第一行一个整数 $T$，表示数据组数。
接下来 $T$ 行，每行四个整数 $n$、$m$、$k$、$p$。
接下来 $T$ 行，每行四个整数 $n$、$m$、$k$、$p$。
输出格式
共 $T$ 行，每行一个数，表示总能量对 $p$ 取模后的结果。
输入输出样例
输入 #1
3 2 2 0 100 3 3 0 100 3 3 1 100
输出 #1
2 12 6
说明/提示
测试点 1 ~ 2：$ T = 5000 $，$ n \leq 100 $，$ m \leq 100 $，$ k \leq 100 $，$ p \leq 10 ^ 9 $；
测试点 3：$ T = 5000 $，$ n \leq 10 ^ {18} $，$ m \leq 10 ^ {18} $，$ k = 0 $，$ p \leq 10 ^ 9 $；
测试点 4：$ T = 5000 $，$ n \leq 10 ^ {18} $，$ m \leq 10 ^ {18} $，$ k = 1 $，$ p \leq 10 ^ 9 $；
测试点 5：$ T = 5000 $，$ n \leq 10 $，$ m \leq 10 ^ {18} $，$ k \leq 10 $，$ p \leq 10 ^ 9 $；
测试点 6：$ T = 1 $，$ n \leq 10 ^ 5 $，$ m \leq 10 ^ {18} $，$ k \leq 10 ^ 5 $，$ p \leq 10 ^ 9 $；
测试点 7：$ T = 1 $，$ n \leq 10 ^ {18} $，$ m \leq 10 ^ {18} $，$ k \leq 10 ^ {18} $，$ p \leq 10 ^ 9 $；
测试点 8：$ T = 100 $，$ n \leq 10 ^ {18} $，$ m \leq 10 ^ {18} $，$ k \leq 10 ^ {18} $，$ p \leq 10 ^ 9 $；
测试点 9 ~ 10：$ T = 5000 $，$ n \leq 10 ^ {18} $，$ m \leq 10 ^ {18} $，$ k \leq 10 ^ {18} $，$ p \leq 10 ^ 9 $。
测试点 3：$ T = 5000 $，$ n \leq 10 ^ {18} $，$ m \leq 10 ^ {18} $，$ k = 0 $，$ p \leq 10 ^ 9 $；
测试点 4：$ T = 5000 $，$ n \leq 10 ^ {18} $，$ m \leq 10 ^ {18} $，$ k = 1 $，$ p \leq 10 ^ 9 $；
测试点 5：$ T = 5000 $，$ n \leq 10 $，$ m \leq 10 ^ {18} $，$ k \leq 10 $，$ p \leq 10 ^ 9 $；
测试点 6：$ T = 1 $，$ n \leq 10 ^ 5 $，$ m \leq 10 ^ {18} $，$ k \leq 10 ^ 5 $，$ p \leq 10 ^ 9 $；
测试点 7：$ T = 1 $，$ n \leq 10 ^ {18} $，$ m \leq 10 ^ {18} $，$ k \leq 10 ^ {18} $，$ p \leq 10 ^ 9 $；
测试点 8：$ T = 100 $，$ n \leq 10 ^ {18} $，$ m \leq 10 ^ {18} $，$ k \leq 10 ^ {18} $，$ p \leq 10 ^ 9 $；
测试点 9 ~ 10：$ T = 5000 $，$ n \leq 10 ^ {18} $，$ m \leq 10 ^ {18} $，$ k \leq 10 ^ {18} $，$ p \leq 10 ^ 9 $。