HDU 6048 Puzzle 逆序對 計數 發現基本操作

8數位問題的擴充，給定一個n*m的局面，問是否有解。局面按題目規則生成。

将此問題稱作擴充8數位問題的話，通過觀察基本操作可以發現，對于x，在隻影響x右下角格子的前提下，我們一定可以移到指定的位置。這樣我們可以依次将1，2，3，...等格子歸位。隻剩下右下角四個格子的順序不定。嚴格的說，是(n,m-1)與(n-1,m)的格子不能确定是否恰好在其位置上。枚舉最簡單的2*2情況可以發現，将數字按照每行每列的順序寫成一個排列後，其逆序對為奇數的時候不可以歸位，偶數的時候可以歸位。這相當于，移到最後，如果右下角四個格子的逆序對數為偶數，整個問題有解，否則整個問題無解。

還可以發現，之前我們的任何操作都不會改變逆序對的個數，因為考慮： 1.空格的橫向移動：排列不發生改變，逆序對奇偶性不改變； 2.空格的豎向移動：相當于做了(m-1)次交換，由于最後空格回到了右下角，即豎向交換的次數為偶數次，設為2K，則總體交換次數為2K*(m-1)次，也不改變逆序對的奇偶性。

故全圖剩右下角四個格子沒處理時，排列的逆序對奇偶性和原問題排列逆序對的奇偶性是一樣的。可以推出，原問題逆序對奇偶性為偶數的時候，有解；反之無解。

在計算逆序對奇偶性的時候，對于每個放入的值，其後面比它小的數相當于留下的插空，這個在演算紙上模拟一下就可以發現，公式可以看代碼。

#include <cstdio>
int T;
long long res,n,m,P;
int main()
{
    scanf("%d",&T);
    while (T--) {
        res=0;
        scanf("%I64d%I64d%I64d",&n,&m,&P);
        n=n*m-1;
        while (n>P) {
            long long t=(n+P-1)/P;
            res+=t*(t-1)*(P-1)/2LL;
            n-=t;
        }
        puts(res%2?"NO":"YES");
    }
    return 0;
}