51NOD 1371填数字

传送门

分析

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

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

const long long mod = 1e8+;

#define add(x,y) x=(x+y)%mod

long long dp[][][];

int main(){

      long long n,now=,i,j,k;

      scanf("%lld",&n);

      dp[][][]=;

      for(i=;i<=n;i++){

          now^=;

          memset(dp[now],,sizeof(dp[now]));

          for(j=;j<i;j++)

            for(k=;k+j<i;k++){

                add(dp[now][j][k+],dp[now^][j][k]);

                add(dp[now][j][k],(k+)*dp[now^][j][k]%mod);

                if(j>)

              add(dp[now][j-][k+],j*dp[now^][j][k]%mod);

                add(dp[now][j+][k],(k+)*dp[now^][j][k]%mod);

                if(j>=)

              add(dp[now][j-][k+],j*(j-)/%mod*dp[now^][j][k]%mod);

                add(dp[now][j][k],j*(k+)%mod*dp[now^][j][k]%mod);

                if(k>)

              add(dp[now][j+][k-],(k+)*k/%mod*dp[now^][j][k]);

            }

      }

      long long Ans=;

      for(j=;j<=n;j++)

        for(k=;k+j<=n;k++)

          add(Ans,dp[now][j][k]);

      printf("%lld\n",Ans);

      return ;

}