本文共 1294 字，大约阅读时间需要 4 分钟。

题目

题目描述

你知道吗？乌拉圭的人口有345.7万，同时，仅澳大利亚就有4700万只袋鼠。

袋鼠决定入侵乌拉圭。袋鼠们将在平原上布阵，平原被划分成 $n\times m$ 的网格。

每个格子里至多有一只袋鼠。

为了抵御袋鼠的入侵，你需要预测敌人的阵型。具体地，你需要计算袋鼠阵

型的数目，满足平原网格中每行、每列的袋鼠数目之和均为$K$.

如果袋鼠入侵了乌拉圭，那么每一个乌拉圭人都要打 14 只袋鼠。你不知道，

你不在乎，你只会在这里写这道无聊的题，你只关心你自己。

数据范围

$1\le n,m\le 9$，$0\le k\le min(n,m)$

题解

题目大意：在$n\times m$的矩阵了填01，问有多少种方案使得每行每列都为$k$

注意到$n,m$特别小，可以采取暴力打表。而容易推出在$k=0$时答案是1，而如果$n\ne m$且$k\ne 0$时无解

那么题目就可以转化成$n\times n$的矩阵，而容易发现$k$与$n-k$是具有对称性的，那么这个题的最大数据就是$n=m=9,k=4$，这个用一个比较优秀的暴力（如记忆化）先跑出来，然后就打表

难得的打表题呀，正解是状压$dp$

Code

#include
   
    #define ll long longusing namespace std;int n,m,k;ll a[15][15]={   {   1},{   1},{   1,2},{   1,6},{   1,24,90},{   1,120,2040}, {   1,720,67950,297200}, {   1,5040,3110940,68938800}, {   1,40320,187530840,24046189440,116963796250}, {   1,362880,14398171200,12025780892160,315031400802720}};;int main(){   	freopen("algebra.in","r",stdin);	freopen("algebra.out","w",stdout);	scanf("%d%d%d",&n,&m,&k);	if (n!=m)	{   		if (k==0) printf("1\n");		else printf("0\n");		fclose(stdin);		fclose(stdout);		return 0;	}	if (2*k>n) k=n-k;	printf("%lld\n",a[n][k]);	fclose(stdin);	fclose(stdout);	return 0;}