ZROI普转提10.13

不爽,连掉两场了…

还是我太菜了啊…

A.控制人偶

$SB$题,如果 $T\le n$ 就直接暴力跑 $n\le 5000$.
否则,就把一整个命令串压成一个矢量,从起点 $(0,0)$ 加 $T/n$ 次.
以这个终点作为起点再暴力跑即可.

B.复杂度计算

直接贴代码能有 $20pts$.
然后,通过阅读代码,我们发现这是统计所有子矩阵的 $size$ 之和.
考虑,一个点会产生多少贡献,即它会被包含在多少个子矩阵中.
令该点为 $(x,y)$ ,那么显然,包含它的子矩阵的左上角一定在 $(1,1)$ 到 $(x,y)$ 之间,右下角一定在 $(x,y)$ 到 $(n,m)$ 之间.
而这两个矩阵的 $size$ 是可以 $\Theta(1)$ 计算的.
所以,只需要枚举每个点,统计其贡献即可,贡献显然为两个矩阵的 $size$ 的乘积.
总复杂度 $\Theta(n^2)$.
然而这远远不足以通过本题.
通过打表可以得到这个东西:

1    4    10   20   35  
4    16   40   80   140 
10   40   100  200  350 
20   80   200  400  700 
35   140  350  700  1225

你惊奇地发现,如果把第一行或者第一列拿出来作为数列 $v_i$.
那么令 $f(i,j)$ 表示 $n=i,m=j$ 时的答案,会有 $f(i,j)=v_i\times v_j$.

那么如果我们能找出这个东西的通项公式,那么就能在 $\Theta(1)$ 的复杂度内求出答案.

如果你学过一些数学你可能会记得有这么一个数列:$1,4,9,16,25,…$

对,没错,这就是完全平方数.然后还有另一个数列:$1,5,14,30,55,…$,没错,这就是上一个数列的前$n$项和得到的数列.

而我们知道这一个数列的通项公式是 $\cfrac{n\times(n+1)\times(2n+1)}{6}$.

而我们要的题目中的数列就是这个东西少一点…然后一顿乱凑,你发现题目中的数列的通项公式是这个东西:$\cfrac{n\times(n+1)\times(n+2)}{6}$.

愉快$AC$?$NO,NO,NO,too \: naive.$.

我们发现$1\le n,m\le 10^{18}$,稍微一运算就会炸,所以要先把$n,m$取模再算.

愉快$AC$.

C.复印任务

咕咕咕…

D.A+B Problem

矩阵加$1$,矩阵求和.经典的二维线段树/二维树状数组题目.
但你分析一下…这个东西 $1\le n,m\le 8000$ , 二维线段树时空双爆.
所以只能二维树状数组,而直接开 $int$ 也是存不下的.
我们注意到,模数 $1\le p \le 256$,所以我们使用 $unsigned \: char$ 存储即可.
剩下的操作和普通的二维树状数组并无不同.