cafelier@SRM

SRM431 Div1 500

あとで | 14:53 |

やっぱり電車の待ち時間で解けるくらい何の変哲もないDPだった…；；

static const long long MODVAL = 1000000007;
int memo[10][11][1001][9];

class MegaCoolNumbers
{
public:
  int count(int N, int A)
  {
    memset(memo, 0xff, sizeof(memo));
    return rec(1, 10, N, A);
  }

  int rec(int D, int F, int N, int A)
  {
    if( A==0 )     return N==0 ? 1 : 0;
    if( N < A )    return 0;
    if( N==1 )     return 10-D - (F==10 ? 0 : 1);
    if( 10-D < A ) return 0;
    if( memo[D][F][N][A] != -1 )
      return memo[D][F][N][A];

    long long ans = 0;
    for(int d=D; d<=9; ++d) if(d!=F)
      for(int k=2; k<=N; ++k)
        for(int q=0; d+(k-1)*q<=9; ++q)
          ans += rec(d+(k-1)*q, min(10, d+k*q), N-k, A-1);
    return memo[D][F][N][A] = int(ans % MODVAL);
  }
};