一道很有趣的题
能空手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,j)表示在序列的第i位有j这个数;
所以该矩阵表示序列 1 4 2 3 5
这样一来 当我们想求解时 就把问题形象化了
我们可以看到 当问题有解时 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