SRM 509 Div2 Medium LuckyReminder

考えられる部分列を全て足しあわせた数を9で割った余りを答える問題.
全ての場合を考えると大変.
最後の二桁がj番目の文字,i番目の文字となるある部分列y[1..m]を考える.
y[1..m-1]を9で割った余りをamariとすると(X[j]+amari)*10+X[i] の余りがy[1..m]の余りとなる.
最後の文字がj番目の文字で余りがamariとなる部分列の数をnum[j][amari]とすると最後の二桁がj番目の文字,i番目の文字となる部分列の余りの総和はnum[j][amari]*(((X[j]+amari)*10+X[i])%9)となる.
num[j][amari]はDPで計算可能なので考えられる最後の二桁の組み合わせを考え,y[1..m]の余りの総和を求め9で割った余りを返せば良い

class LuckyRemainder
{ 
public: 
  int getLuckyRemainder(string X) 
    { 
      int n = X.size();
      vector<vector<long long> >  num(n, vector<long long>(9, 0));
      vector<int> Y(n,0);
      int res = 0;
      int i, j, k;
      for(i = 0; i < n; i++) {
        Y[i] = X[i]-'0';
        num[i][0] = 1;
      }
      for(i = 0; i < n; i++){
        res = (res + Y[i]) % 9;
        for(j = 0; j < i; j++){
          for(k = 0; k < 9; k++) if (num[j][k] > 0){
            res = (res + num[j][k]*((k + Y[j]) * 10 + Y[i])%9) % 9;
            num[i][((k+Y[j]) * 10)%9] += num[j][k];
          }
        }
      }
      return res;
    } 

};