51NOD 1371填数字-白红宇

51NOD 1371填数字

阅读量：6209 次

发布时间：2019-06-21

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

分析

此题关键在于想出dp[i][j][k]代表考虑到第i行，还能放1的的共有j列，还能放2的共有k行。之后就枚举每一行是没有还是1个1还是2个1还是1个2，然后转移即可。

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;const long long mod = 1e8+7;#define add(x,y) x=(x+y)%modlong long dp[2][210][210];int main(){ long long n,now=0,i,j,k; scanf("%lld",&n); dp[0][0][0]=1; for(i=1;i<=n;i++){ now^=1; memset(dp[now],0,sizeof(dp[now])); for(j=0;j
                   
                    0) add(dp[now][j-1][k+1],j*dp[now^1][j][k]%mod); add(dp[now][j+1][k],(k+1)*dp[now^1][j][k]%mod); if(j>=2) add(dp[now][j-2][k+1],j*(j-1)/2%mod*dp[now^1][j][k]%mod); add(dp[now][j][k],j*(k+1)%mod*dp[now^1][j][k]%mod); if(k>0) add(dp[now][j+2][k-1],(k+1)*k/2%mod*dp[now^1][j][k]); } } long long Ans=0; for(j=0;j<=n;j++) for(k=0;k+j<=n;k++) add(Ans,dp[now][j][k]); printf("%lld\n",Ans); return 0;}