Tamflexの貯蔵庫

やる気のない備忘録

aoj 0070

組み合わせの個数 | Aizu Online Judge

dfsでやるとTLEしてしまった...

int a[10];
int n, s, cnt;

void dfs(int m,int r)
{
  if(r > s) return;
  if(m==n+1)
  {
    if(r==s) cnt++;
    return;
  }
  FOR(i,0,9)
  {
    if(a[i])
    {
      a[i] = 0;
      dfs(m+1,r+m*i);
      a[i] = 1;
    }
  }
}

void solve()
{
  cnt = 0;
  fill_n(a,10,1);
  dfs(1,0);
  cout << cnt << endl;
}

int main()
{
  while(cin >> n >> s) solve();
  return 0;
}

全探索しても大した量ではないのでメモしていける

int a[10];
int T[11][335];

void memo(int m,int s)
{
  if(m>11) return;
  FOR(i,0,9)
  {
    if(a[i])
    {
      a[i] = 0;
      T[m][s+m*i]++;
      memo(m+1,s+m*i);
      a[i] = 1;
    }
  }
}

void init()
{
  fill_n(a,10,1);
  REP(i,11) fill_n(T[i],335,0);
  memo(1,0);
}

int main()
{
  init();
  int n, s;
  while(cin >> n >> s) cout << (s>330?0:T[n][s]) << endl;
  return 0;
}