不爽,连掉两场了...
还是我太菜了啊...
\(SB\)题,如果 \(T\le n\) 就直接暴力跑 \(n\le 5000\).
否则,就把一整个命令串压成一个矢量,从起点 \((0,0)\) 加 \(T/n\) 次.
以这个终点作为起点再暴力跑即可.
直接贴代码能有 \(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\).
咕咕咕...
矩阵加\(1\),矩阵求和.经典的二维线段树/二维树状数组题目.
但你分析一下...这个东西 \(1\le n,m\le 8000\) , 二维线段树时空双爆.
所以只能二维树状数组,而直接开 \(int\) 也是存不下的.
我们注意到,模数 \(1\le p \le 256\),所以我们使用 \(unsigned \: char\) 存储即可.
剩下的操作和普通的二维树状数组并无不同.
原文：https://www.cnblogs.com/Equinox-Flower/p/11668347.html