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

1371 填数字

有n行格子，第i(1<=i<=n)行有i个格子，每行格子是左对齐。现在要在每一个格子填入一个非负整数，最后使得每一行每一列的和都不超过2。

请计算有多少种方案，答案比较大，请输出对100,000,007(1e8+7)取余后的结果。

下图是n=4的时候格子的摆放。

输入

第1行：给出一个整数n (1<=n<=200)。

输出

对于每个测试用例，输出结果占一行。

输入样例

1

输出样例

3

代码

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;typedef long long ll;const ll mod = 1e8 + 7;ll dp[210][210][210];int main() { ll n; cin >> n; dp[0][0][0] = 1; // 第i行 for (ll i = 1; i <= n; i++) { // 有j列和为1 for (ll j = 0; j <= i; j++) { // 有k列和为2 for (ll k = 0; k <= (i - j); k++) { dp[i][j][k] = dp[i - 1][j][k]; if (j - 1 >= 0) { // 第i行放一个1在列和为0的位置 dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - 1][k] * (i - j - k + 1)) % mod; } if (j - 2 >= 0) { // 第i行放两个1在列和为0的位置 dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - 2][k] * (i - j - k + 2) * (i - j - k + 1) / 2) % mod; } if (k - 2 >= 0) { // 第i行放两个1在列和为1的位置 dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j + 2][k - 2] * (j + 2) * (j + 1) / 2) % mod; } if (k - 1 >= 0) { // 第i行放一个1在列和为1的位置 dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j + 1][k - 1] * (j + 1)) % mod; // 第i行放一个1在列和为1的位置，放一个1在列和为0的位置 dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1] * j * (i - j - k + 1)) % mod; // 第i行放一个2在列和为0的位置 dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1] * (i - j - k + 1)) % mod; } } } } ll ans = 0; for (ll i = 0; i <= n; i++) { for (ll j = 0; j <= n; j++) { ans = (ans + dp[n][i][j]) % mod; } } cout << ans << endl; return 0;}
          
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/weixin_43820352/article/details/110493818 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！