解析
棋盘上黑白格染色. 曼哈顿距离偶数: 奇偶性相同.
枚举有几种颜色分到白格, 组合数计算即可.
注意预处理, 时间还是比较宽裕的.
为了不重复计数, 考虑枚举严格用了 i 种颜色, 我们再枚举分配 j 种给白集合. 设白集合, 黑集合大小分别为 s1,s2, 那么这种分配方案对答案的贡献为 \(C^k_i\) \(C^k_i\) \(f_{s1,j}\) \(f_{s2,i-j}\) \(j!\) \((i-j)!\)
\(f_{i,j}\) 表示第二类斯特林数, 表示将 i 个数分配到 j 个集合的方案数.
- \(f_{
- i,j
- }\) = \(f_{
- i-1,j-1
- }\) + \(f_{
- i-1,j
- }\) \(\times j\)
- \(f_{
- 0,i
- }\) = \(0^i\)
这些东西都可以预处理.
注意边界要开好, 不然 n=1,m=1 情况会错.
时间复杂度 $ O(n^2 m^2+qK^2) $.
代码
- #include<bits/stdc++.h>
- using namespace std;
- const long long p=1000000007;
- int T,n,m,k,s1,s2;
- long long c[410][410],f[410][60],fact[410],ans;
- bool mape[25][25];
- int main(){
- scanf("%d",&T);
- c[0][0]=1;c[1][0]=c[1][1]=1;
- for(int i=2;i<=405;++i){
- for(int j=0;j<=i;++j){
- c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;
- }
- }
- f[0][0]=1;
- for(int i=1;i<=405;++i){
- for(int j=1;j<=50&&j<=i;++j){
- f[i][j]=(f[i-1][j]*j+f[i-1][j-1])%p;
- }
- }
- fact[0]=1;
- for(int i=1;i<=405;++i){
- fact[i]=(long long)i*fact[i-1]%p;
- }
- while(T--){
- scanf("%d %d %d",&n,&m,&k);
- s1=0,s2=0;
- for(int i=1;i<=n;++i){
- for(int j=1;j<=m;++j){
- mape[i][j]=(i&1)^(j&1);
- s1+=mape[i][j];
- s2+=1^mape[i][j];
- }
- }
- ans=0;
- for(int i=1;i<=k;++i){
- for(int j=0;j<=i;++j){
- (ans+=(((((c[k][i]%p*c[i][j])%p*f[s1][j])%p*f[s2][i-j])%p*fact[j])%p*fact[i-j])%p)%=p;
- }
- }
- printf("%lld\n",ans%p);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3171403.html