P1497 木牛流马 题解
qwq___qaq
2021-09-10 14:03:20
### 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;
}
```