Note: This article is available in Chinese only. 本文暂无英文版本。
View original
http://acm.hdu.edu.cn/showproblem.php?pid=6048
题意：#
有 n * m - 1 个数，每次选择第 1,p + 1,p * 2 + 1….. 的顺序选择数，先按左到右，再按从上到下的顺序填入n * m 的格子，空格子可以和相邻的数字交换位置，问最后能否在格子中形成 1~ n * m - 1的数按从左到右，从上到下的顺序。
思路：#
傻逼结论题。
根据九宫格问题的结论：将矩阵中的数按先从左到下右再从上到下排成一列，其逆序对如果为偶数则一定有解，否则一定无解
根据九宫格问题的结论：将矩阵中的数按先从左到下右再从上到下排成一列，其逆序对如果为偶数则一定有解，否则一定无解
根据九宫格问题的结论：将矩阵中的数按先从左到下右再从上到下排成一列，其逆序对如果为偶数则一定有解，否则一定无解
然后我们可以观察发现，按照题目中填数的策略
按照填入的顺序，每个数对逆序对的贡献分别是0,p-1,2_(p-1)… 0,p-1,2_(p-1)…
注意到当总数小于等于p时，所有数对逆序对就没有贡献了。
然后直接算等差数列就好了。
\[ \text{sum} = n \cdot a_1 + \frac{n(n-1)}{2} \cdot d \]由于首项一直为0，所以只要算后面那部分就好了。
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2017年11月06日 星期一 18时45分04秒
4File Name :6048.cpp
5************************************************ */
6
7#include <bits/stdc++.h>
8#define PB push_back
9#define fst first
10#define sec second
11#define lson l,m,rt<<1
12#define rson m+1,r,rt<<1|1
13#define ms(a,x) memset(a,x,sizeof(a))
14typedef long long LL;
15#define pi pair < int ,int >
16#define MP make_pair
17
18using namespace std;
19const double eps = 1E-8;
20const int dx4[4]={1,0,0,-1};
21const int dy4[4]={0,-1,1,0};
22const int inf = 0x3f3f3f3f;
23int n,m,p;
24int tot;
25LL ans;
26int main()
27{
28 #ifndef ONLINE_JUDGE
29 freopen("./in.txt","r",stdin);
30 #endif
31 int T;
32 cin>>T;
33 while (T--)
34 {
35 scanf("%d %d %d",&n,&m,&p);
36 int tot = n*m-1;
37 ans = 0;
38 while (tot>p) //when tot<p,the ans is 1
39 {
40 int num = (tot-1)/p+1; // 项数
41 LL tmp = num*(num-1)/2*(p-1);
42 ans = ans + tmp;
43 tot-=num;
44 }
45 printf("%s\n",ans%2LL?"NO":"YES");
46 }
47 #ifndef ONLINE_JUDGE
48 fclose(stdin);
49 #endif
50 return 0;
51}