题目：
我是超链接
翻译一下：
n×m的网格。最初全是白色的，将p个格子染黑，要求黑格子两两没有公共边。求方案数。
n×m≤80，p≤20
题解：
状压dp入门
nm≤80，至少存在一个变量不超过8。
f[i][j][k]表示前i行安排j个黑格子，第i行的状态是k，方案数。
没用long long卡了n久n久。。。。。。
代码：
#include <cstdio> #include <iostream> #include <cstring> #define LL long long using namespace std; //f[i][j][k]表示前i行安排j个黑格子，第i行的状态是k，方案数。 int n,m,k;LL f[85][25][1<<12]; bool cf(int n) { int bit[15],cnt=0; while (n) bit[++cnt]=(n&1),n>>=1; for (int i=2;i<=cnt;i++) if (bit[i] && bit[i-1]) return false; return true; } bool ll(int ks,int s) { for (int i=0;i<15;i++) if ((ks&(1<<i)) && (s&(1<<i))) return false; return true; } LL gcd(LL a,LL b) { LL c=a%b; if (c==0) return b; else return gcd(b,c); } void C(int n,int m,LL ans) { int i,j; LL xi=1,sh=1,f; for (i=1;i<=m;i++) xi*=i; for (i=n-m+1;i<=n;i++) { sh*=i; f=gcd(xi,sh); xi/=f; sh/=f; } xi*=ans; f=gcd(xi,sh); xi/=f; sh/=f; printf("%I64d/%I64d",sh,xi); } int main() { int i,j,s,ks;LL ans=0; scanf("%d%d%d",&n,&m,&k); if (m>n) swap(n,m); f[0][0][0]=1; for (i=1;i<=n;i++) for (j=0;j<=k;j++) for (s=0;s<(1<<m);s++) { int cnt=0; if (!cf(s)) continue; int hh=s; while (hh) cnt+=(hh&1),hh>>=1; if (cnt>j) continue; for (ks=0;ks<(1<<m);ks++) { if (!cf(ks)) continue; if (!ll(ks,s)) continue; f[i][j][s]+=f[i-1][j-cnt][ks]; } } for (i=0;i<(1<<m);i++) ans+=f[n][k][i]; if (ans<=0) printf("Impossible!"); else C(n*m,k,ans); }