P1497 木牛流马 题解

### Update 2023/2/23 修改了错别字（你用 $\rightarrow$ 利用，初一 $\rightarrow$ 除以） *** 对于初始状态： 第一个全都空着，可以选择 $n^2$ 个； 第二个被删去了一行一列，只可以选择 $(n-1)^2$ 个； …… 同理，第 $k$ 个木牛流马删去了 $k-1$ 行和 $k-1$ 列方法数即为 $(n-k+1)^2$。 利用乘法原理，我们可以得到 $s\gets n^2\times(n-1)^2\times...\times(n-k+1)^2$。初始完毕后，就是计算了，还是输入 $t$，但此时我们就可以直接用初始状态直接除以 $t$ 的阶乘，复杂度就更低了。并且此时不需特判，因为如果 $n<k$，那么 $s$ 一定乘了一次 $0$，但还是要注意 `long long` 的问题。 ```cpp #include<bits/stdc++.h> #define int unsigned long long using namespace std; int jc(int t){ if(t==0) return 1; int sum=1; for(int i=2;i<=t;i++) sum*=i; return sum; }//阶乘 int t,s=1,n,k,h;//s一定要为1 signed main(){ cin>>n>>k>>h; for(int i=1;i<=k;i++) s*=pow(n-i+1);//初始化 while(h--){ cin>>t; s/=jc(t); } cout<<s<<endl; return 0; } ```