P6608 - 驴鞍数

题目

P6608驴鞍数

限制 : 时间限制 : 20000 MS 空间限制 : 524288 KB

评测说明 : 2s,512MB

问题描述

众所周知，一个数字矩阵可能存在马鞍数：这个数是所在行的最小值，同时也是所在列的最大值。为了方便起见，规定整个数字矩阵中的数都互不相同，这样就不会出现并列的情况。

nodgd觉得马鞍数太无聊了，于是定义了数字矩阵的驴鞍数：这个数在所在行中的从小到大排名和这个数在所在列中的从大到小排名相同。仍然规定整个数字矩阵的数都互不相同，避免并列。

nodgd的问题也很简单，就是请你计算一下某个数字矩阵中有多少个驴鞍数。

输入格式

输入一行两个整数$n,y$，其中$n$是矩阵的大小，$y$是数据生成器的种子。生成矩阵的规则如下：

首先利用以下代码的$\texttt{permu}$函数生成一个$0,1,\dots,n^2-1$的排列${a_0,\dots,a_{n^2-1}}$

unsigned int x = 19260817, y;	//y是读入的种子
inline unsigned int get() {
    x ^= y >> 11;
    y ^= x >> 15 << 17;
    x ^= (y & 0xabcdef) + 20200308;
    return x ^ ~y;
}
void permu(int n, unsigned int a[]) {	//n是读入的矩阵大小
    for (unsigned int i = 0; i < n * n; i ++) {
        unsigned int j = get() & i;
        a[i] = a[j];
        a[j] = i;
    }
}

然后按如下方式填入矩阵：

\[ \left[ \begin{matrix} a_0 & a_1 & \cdots & a_{n-1}\\ a_n & a_{n+1} & \cdots & a_{2n-1}\\ \vdots & \vdots & \ddots & \vdots\\ a_{n^2-n} & a_{n^2-n+1} & \cdots & a_{n^2-1} \end{matrix} \right] \]

输出格式

输出一个整数，即矩阵中驴鞍数的个数。

提示

输入输出样例1

样例输入

1 0

样例输出

输入输出样例2

样例输入

2 1234

样例输出

样例说明

\[ \left[ \begin{matrix} 3 & 0 \\ 2 & 1 \end{matrix} \right] \]

其中$1,2$都是驴鞍数。

输入输出样例3

样例输入

3 34567

样例输出

样例说明

\[ \left[ \begin{matrix} 8 & 7 & 6\\ 1 & 0 & 3\\ 2 & 5 & 4 \end{matrix} \right] \]

其中$3,4,6$都是驴鞍数

输入输出样例4

样例输入

666 666666

样例输出

数据规模与约定

测试点		0		1		2		3		4		5		6		7		8		9
$n=$		88		111		222		444		777		999		3333		4444		5555		6666

对于样例数据和所有测试数据，$1\leq n\leq 6666$，$0\leq y\lt2^{32}$。