洛谷1377 M国王(SCOI 2005相互不可侵King)

洛谷1377 M国王(SCOI 2005相互不可侵King)
本題の住所: http://www.luogu.org/problem/show?pid=1377
タイトルの説明
   毎日n皇后で、どんなにつまらないことか.m王のゲームをしよう!   タイトルは、n*nの格子にm個の王を入れて、お互いに攻撃しないようにするには、何種類の置き方がありますか?(0)   王の攻撃力は皇后に及ばず、隣接する8つの格子にしか攻撃できなかった.
にゅうしゅつりょくけいしき
入力形式:
n,m
出力フォーマット:
シナリオ数
入出力サンプル
サンプル#1を入力:
1 1
出力サンプル#1:
1
説明
データ範囲:100%のデータはn<=8を満たし、m<=n*n時限は2秒(正常コードが時限内に通過することを保証する)
 
 
【考え方】
   状態圧縮DP.
   この問題とn皇后の違いに注意してください.複数の王が同じ行に置くことができます.
   d[i][s 1][j]は、i行目i行目i行目に置かれた状態がs 1であり、j個が置かれたシナリオ数を示すものとする.sはバイナリで表される.移行方程式は次のとおりです.
     d[i][s1][j] += d[i-1][s2][j-cnt[s1]]
   ここでcntは状態に置かれた王の数を表す.
   最適化:各状態が役に立つわけではないし、両方の状態が互いに移行できるわけではないことに注意してください.したがって、状態間のエッジ(has_edge)を確立しながら、自身が要求に合致しない状態(can)を事前にふるい取ることができる.
 
【コード】

 1 #include
 2 #include
 3 using namespace std;
 4 
 5 const int maxn = 1<<9;
 6 
 7 typedef long long LL;
 8 LL d[9][maxn][9*9];
 9 int cnt[maxn];
10 bool has_edge[maxn][maxn];
11 bool can[maxn];
12 int n,m,all;
13 
14 void get_edge() {
15     for(int i=0;iif((i&i>>1)==0)
16     {
17        can[i]=true;
18        for(int j=0;jif(i&(1<;
19        for(int j=0;j) 
20           if(((i&j)==0) && ((i>>1)&j)==0 && ((j>>1)&i)==0) 
21              has_edge[i][j]=true;
22     }
23 }
24 
25 int main() {
26     cin>>n>>m;
27     all=1<<n;
28     
29     get_edge();
30     for(int s=0;sif(can[s]) d[1][s][cnt[s]]=1;
31     
32     for(int i=2;i<=n;i++)
33        for(int s1=0;s1if(can[s1])
34           for(int j=cnt[s1];j<=m;j++)
35           {
36              for(int s2=0;s2if(can[s2] && has_edge[s1][s2])
37                 d[i][s1][j] += d[i-1][s2][j-cnt[s1]];
38           }
39     LL ans=0;
40     for(int s=0;s d[n][s][m];
41     cout<<ans;
42     return 0;
43 }

   また、バイナリの演算優先度に注意し、不確定な場合はカッコをつけます.