Background
有一个n*m的棋盘(n、m≤80,n*m≤80)要在棋盘上放k(k≤20)个棋子，使得任意两个棋子不相邻（每个棋子最多和周围4个棋子相邻）。求合法的方案总数。
Input
本题有多组测试数据，每组输入包含三个正整数n,m和k。
Output
对于每组输入，输出只有一个正整数，即合法的方案数。
Sample Input
2 2 3 4 4 1
Sample Output
0
16
挺基础的一道状压dp啦，然而瞄了一眼题解就没有开long long，wa了一中午。
然而题解开int过了，非酋表示不服。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m,p,tp,a[1005],b[1005];
long long ans,f[85][25][1005];
void dfs(int num,int lst,int now,int cnt)
{if(num==m){++tp;a[tp]=now;b[tp]=cnt;return ;}dfs(num+1,lst,now,cnt);//不选 if(num-lst>=2&&cnt<p)//选 dfs(num+1,num,now|(1<<num),cnt+1);
}
int main()
{while(scanf("%d%d%d",&n,&m,&p)==3){tp=ans=0;memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(f,0,sizeof(f));if(n<m)swap(n,m);dfs(0,-2,0,0);f[0][0][0]=1;for(int i=1;i<=n;i++)for(int j=1;j<=tp;j++)//上一行摆放状态 for(int g=0;g<=p;g++)//前(i-1)行的棋子总数 if(f[i-1][g][a[j]]>0)for(int k=1;k<=tp;k++)if((a[j]&a[k])==0&&g+b[k]<=p)f[i][g+b[k]][a[k]]+=f[i-1][g][a[j]];for(int i=1;i<=tp;i++)ans+=f[n][p][a[i]];printf("%lld\n",ans);}return 0;
}