hdu 6048 | 2017 Multi-University Training Contest - Team 2 D Puzzle (结论题)
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时，所有数对逆序对就没有贡献了。
然后直接算等差数列就好了。
$$ sum = n_a_{1} + \frac{n_(n-1)}{2}*d $$
由于首项一直为0，所以只要算后面那部分就好了。
/* ***********************************************
Author :111qqz
Created Time :2017年11月06日 星期一 18时45分04秒
File Name :6048.cpp
************************************************ */
1#include <bits/stdc++.h>
2#define PB push_back
3#define fst first
4#define sec second
5#define lson l,m,rt<<1
6#define rson m+1,r,rt<<1|1
7#define ms(a,x) memset(a,x,sizeof(a))
8typedef long long LL;
9#define pi pair < int ,int >
10#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6int n,m,p;
7int tot;
8LL ans;
9int main()
10{
11 #ifndef ONLINE_JUDGE
12 freopen("./in.txt","r",stdin);
13 #endif
14 int T;
15 cin>>T;
16 while (T--)
17 {
18 scanf("%d %d %d",&n,&m,&p);
19 int tot = n*m-1;
20 ans = 0;
21 while (tot>p) //when tot<p,the ans is 1
22 {
23 int num = (tot-1)/p+1; // 项数
24 LL tmp = num*(num-1)/2*(p-1);
25 ans = ans + tmp;
26 tot-=num;
27 }
28 printf("%s\n",ans%2LL?"NO":"YES");
29 }
30 #ifndef ONLINE_JUDGE
31 fclose(stdin);
32 #endif
33 return 0;
34}