一道很有趣的题
能空手AC的都是大佬
乍一看 感觉跟递推没啥大关系（）
事实上 我们要把这个问题展开成一个二维的平面（能想出来这个的我sto orz sto orz sto orz sto orz sto orz sto orz sto orz sto orz sto orz sto orz）
形如
1 0 0 0 0
0 0 0 1 0
0 1 0 0 0
0 0 1 0 0
0 0 0 0 1
我们把矩阵的行i和列j定义为 ：（i，ｊ）表示在序列的第ｉ位有ｊ这个数；
所以该矩阵表示序列 １ ４ ２ ３ ５
这样一来 当我们想求解时 就把问题形象化了
我们可以看到 当问题有解时 a[i] 是 单调不降的
因为不可能存在当前i个序列位有a[i]个比i小的数 但前i + 1 个却有a[i + 1]个比i小的数 且a[i + 1] < a[i] i越大反而越少
并且我们知道 bi是随机的（只要在1 - n且不重复即可）
所以我们可以考虑用a[i] 转移
那联系到刚才的矩阵 a[i]又表示什么呢（？）
不难看出 每次转移时 转移所用的序列长为 i 并且此时的n也等于i（长为i其实也就是n为i） 所以a[i]掌管了前i *i个位置
那么也就是说 a[i] 表示 矩阵的前i * i位中有几个1
我们来证明一下：
在i * i的矩阵当中
行数为i 则满足"序列前i个位置"
列数为i 则满足“小于等于i的数”（因为此时的最大值n等于i 而b满足元素范围为1 - n）；
则 成立
那么我们就考虑一下转移：
每次转移时 我们就可以考虑a[i] 和 a[i - 1] 的关系
当a[i] - a[i -1] < 0时 则如我们所说 不满足单调不降 则无解 直接输出0 结束程序
当a[i] - a[i -1] == 0时 也就是说 前i位被限制的数的个数和前i + 1位限制的个数一致 根据此题转移的单调不减的性质 则不需要任何的变动
当a[i] - a[i -1] == 1时 也就是说 我们需要在这个已经填充好的i * i的矩阵外面1层再填一个1 满足在横纵方向不与任何一个已经填好的1相交
此时我们来考虑答案
当矩阵长宽均为i时 矩阵面积为i * i 当矩阵长宽均为i - 1时 矩阵面积为（i - 1） * （i - 1）；
则多出来的面积为i * i - (i - 1) * (i - 1) = 2 * i - 1；
那也就是说 我们有2 * i - 1个位置可以用来填数
但是 别忘了我们所述的不相交的特性
所以 我们必须避开已经填好的数
在(i - 1) * (i -1 ) 的矩阵中 我们已经填好了a[i - 1]个数 那也就是说 有 2 * a[i -1]个位置是不能填的 因为他们已经被填上后 他们所在那一行和那一列就不能再填了
那么此时 转移方程就出来了：
a n s ∗ = ( i ∗ 2 − 1 − 2 ∗ a [ i − 1 ] )；
当a[i] - a[i -1] == 2时 也就是说 我们需要在这个已经填充好的i * i的矩阵外面1层再填两个1 满足在横纵方向不与任何一个已经填好的1相交
此时我们来考虑答案
在一个i * i的矩阵中 他每行 / 列都比（i - 1） * （i - 1）的矩阵多1
然而别忘了 行与列有一个相交点 那就是 （i，i）；
那也就是说 其实多出来的是 i + i - 1个位置
如果我们想保证之前所提到的不重合的要求成立 又想满足在外圈同时填两个数 那么 （i ，i）这个点就是万万不能填的了 因为填上它以后 无论是行还是列都会与另一个被填的数相交
那么也就是说 我们又失去了一个位置
此时 我们还有i + i - 1 - 1个位置
我们把二维压回一维来看
是不是也就相当于 我们在每行 / 列 多了 i - 1个位置（？）
同理于上文 我们还要去掉已经填好的a[i - 1]个位置
那么相对于每行 / 列而言 我们可填的位置有（i - 1 - a[i - 1]）个
根据乘法原理 我们即可统计答案
a n s ∗ = pow(( i − 1 − a [ i − 1 ] )，2)；
当a[i] - a[i -1] > 2时 不难看出 此时无论怎么填 都会存在行列相交的情况（如果不理解行列相交 请移步八皇后问题 想象此问题为在斜线上可以相交的N皇后问题）
则 无解 输出0 结束程序
到此 此题完成
很爽的一道题 博客写了好久 改天再润色
上代码：
1 #include <iostream>
2 #include <algorithm>
3 #include <cmath>
4 #include <cstdio>
5 #include <climits>
6 #include <cassert>
7 #include <cstring>
8 #include <cstdlib>
9 #include <cctype>
10 #include <iomanip>
11 #include <utility>
12 #include <set>
13 #include <map>
14 #include <list>
15 #include <stack>
16 #include <queue>
17 #include <deque>
18 #include <vector>
19 #include <bitset>
20 #include <ctime>
21 #define int long long
22 #define ll long long
23 #define ull unsigned long long
24 #define re register
25 #define mod1 998244353
26 #define mod2 100000007
27 #define lowbit(x) x & (-x)
28 #define gcd(a,b) __gcd(a,b)
29 #define mid ((l + r) >> 1)
30 #define rep(i,a,b) for(re int i(a);i <= b;++ i)
31 #define rrep(i,a,b) for(re int i(a);i >= b;i --)
32 using namespace std;
33 inline int read(){
34 re int x = 0,f = 1;
35 re char ch = getchar();
36 while(ch < '0' || ch > '9'){
37 if(ch == '-') f = -1;
38 ch = getchar();
39 }
40 while(ch >= '0' && ch <= '9'){
41 x = (x << 3) + (x << 1) + (ch ^ 48);
42 ch = getchar();
43 }
44 return x * f;
45 }
46 //#define OJ
47 //#define debug
48 const int mod = 340610;
49 const int M = 1e5 + 1;
50 int a[M];
51 int ans = 1;
52
53 signed main(){
54 #ifdef OJ
55 freopen(".in","r",stdin);
56 freopen(".out","w",stdout);
57 #endif
58 int n = read();
59 rep(i,1,n){
60 a[i] = read();
61 }
62 rep(i,2,n){
63 int x = a[i] - a[i - 1];
64 if(x > 2 || x < 0){
65 cout << 0 << endl;
66 return 0;
67 }
68 if(x == 0){
69 continue;
70 }
71 if(x == 1){
72 ans *= (i * 2 - 1 - 2 * a[i - 1]);
73 ans %= mod;
74 }
75 if(x == 2){
76 ans *= pow((i - 1 - a[i - 1]),2);
77 ans %= mod;
78 }
79 }
80 printf("%lld\n",ans % mod);
81 #ifdef debug
82 printf("\nTime used = %lf", (double)clock() / CLOCKS_PER_SEC);
83 #endif
84 return 0;
85 }
今天是2022.10.3
CSP 动力 ++
NOIP 动力 ++
We‘re ready for fighting int the night!
标签：orz,1.1,ybtoj,sto,矩阵,个数,include,我们,define From： https://www.cnblogs.com/Eruption/p/16749991.html