站外题求助——计数 DP
虽然我也明白这个题目不应该错但是……
给定一个含有 n×m 个格子的珠宝箱，每个格子可以放一颗宝石，要使得每一行，每一列都有一个宝石，问有多少放法满足条件？答案对 109+7 取模
考虑用 DP 做，设 fi,j 表示前 i 行，总共有 j 列上已经放了宝石的方案数，递推式子如下：
\; \sum_{k = 1}^{m - j} f_{i - 1, j - k} \times C_{m - j + k}^{k} \times 2^{j - k} \end{cases}$$ 我用刷表法写的代码： ```cpp #include<bits/stdc++.h> #define MAXN 110 #define MOD 1000000007 using namespace std; typedef long long ll; int n, m; ll dp[MAXN][MAXN], com[MAXN][MAXN], bit[MAXN]; void pre_work(){ com[0][0] = com[1][0] = com[1][1] = 1; for(int i = 2; i <= 100; i++){ com[i][0] = 1; for(int j = 1; j <= i; j++){ (com[i][j] = com[i - 1][j] + com[i - 1][j - 1]) %= MOD; } } bit[0] = 1; for(int i = 1; i <= 100; i++){ (bit[i] = bit[i - 1] * 2) %= MOD; } } int main(){ pre_work(); scanf("%d%d",&n,&m); dp[0][0] = 1; for(int i = 1; i <= n; i++){ for(int j = 0; j <= m; j++){ for(int k = 1; k + j <= m; k++){ (dp[i][j + k] += dp[i - 1][j] * com[m - j][k] * bit[j]) %= MOD; } (dp[i][j] += dp[i - 1][j] * (bit[j] - 1)) %= MOD; } } printf("%lld\n",dp[n][m]); return 0; } ``` 但是错了一些比如： ``` 55 66 ``` 正确答案是 ``` 760879257 ``` 我的输出是 ``` 328259237 ``` 求助大佬加载中...