[TIOJ 1264] 保加利亞的色彩繽紛

作法：

這題我找規律猜到了答案，可是不會證QQ

首先可以先把整個棋盤分成兩部分，假設對他黑白塗色(和題目要求的塗成黑色無關)，使得黑白不相鄰，那麼黑色和白色的部分可以分開處理，因為如果要占領某一部份的格子，一定是把另一部份的格子塗色。

不妨設 n<=m ，另一個重要的觀察是，其實只要先決定其中一格的放法，剩下的就可以用這個全部推出來了，所以解數只有 0 或 1 或 4 這三種。 n = 1 , 2 的情形不難找出來，然後畫一下會發現 n 是奇數的時候都無解，至於 n 是偶數時，我畫了 n = 4 , 6 , 8 的情形，發現他們的解數分別會變成 5 , 7 , 9 一循環，並且在  n = 6 和 8 的時候，會有：當 m = -1 (mod n+1) 時解數為4，當 m = 1 or -3 (mod n+1) 時解數為1，剩下為0，但 n = 4 時有例外。於是我直接猜這件事就過了，但一直證不出來QQ 模 n+1 一循環不難證，剩下的就不知道怎麼辦了@@......

/*
先把要證的東西暫時放在這裡@@

有一個 n*m 的棋盤，滿足 6 <= n <= m ，且n是偶數。證明可以把棋盤的一些格子塗黑使得每個格子恰和一個黑格相鄰(上下左右)，若且唯若 m = 1 or -1 or -3 ( mod n+1 )
*/


code :

#include<bits/stdc++.h>
using namespace std;
 
int l[1000],r[1000] ;
int solve(int n,int m)
{
    if(n==1)
    {
        if(m<=3) return m-1 ;
        if(m%2==0) return 1 ;
        if(m%4==3) return 2 ;
        return 0 ;
    }
    if(n==2) return (m%3==2) ? 4 : 1 ;
    if(n%2) return 0 ;
    if(n==4) return m%5==1 ? 1 : ((m%5==4||m%5==2)?4:0) ;
 
    if(m%(n+1)==n) return 4 ;
    else if(m%(n+1)==1) return 1 ;
    else if(m%(n+1)==(n-2)) return 1 ;
    return 0 ;
}
 
main()
{
    int n,m ;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n>m) swap(n,m) ;
        printf("%d\n",solve(n,m)) ;
    }
}