読者です 読者をやめる 読者になる 読者になる

UVa11472 BeautifulNumbers

解法
BITDP。
leading0を除くために数字は先頭から埋めていくと考えてdpの初期状態から i=0 をはじくと良い。ここで結構詰まった。
また、和においてMODを取る問題ではオーバーフロー対策のために数値を加算するたびにMODを取っていくことを忘れない。

#include <iostream>
#include <algorithm>
#include <numeric>
#include <cstring>

using namespace std;

typedef long long ll;
ll const MOD = 1000000007LL;

ll dp[101][1<<10][10];
int main() {
  int Tc; cin >> Tc;
  while(Tc--) {
    
    int N, M; cin >> N >> M;
    memset(dp, 0, sizeof dp);
    for(int i=1; i<N; i++) {
      dp[1][1<<i][i] = 1;
    }
    for(int i=1; i<M; i++) {
      for(int j=1; j<(1<<N); j++) {
        for(int k=0; k<N; k++) {
          int J = j|(1<<k);
          if(k-1>=0) { (dp[i+1][J][k] += dp[i][j][k-1]) %= MOD; }
          if(k+1 <N) { (dp[i+1][J][k] += dp[i][j][k+1]) %= MOD; }
        }
      }
    }
    
    
    ll sum = 0;
    for(int i=1; i<=M; i++)
      for(int j=0; j<N; j++)
        (sum += dp[i][(1<<N)-1][j]) %= MOD;
    
    cout << sum << endl;
  }
  return 0;
}