cafelier@SRM

SRM484 550

あとで | 13:15 |

• だいたいあってた。
  • A[端!a]::=U[端!a] U U U ... U U U U[端!a]
• これが間違いで
  • A[端!a]::=U[端!a]*
• こうすべきだった。でないと結局aがくっついて消えちゃう
• 自分で "端" とかいう微妙な概念を作ってしまってセルフメダパニしてしまった

static const LL MODVAL = 1000000007;

class PuyoPuyo { public:
   int theCount(int L, int N) 
   {
      vector<LL>           A4(N+1), A3(N+1);
      vector< vector<LL> > U(L, vector<LL>(N+1));

      A4[0] = A3[0] = U[L-1][1] = 1;
      for(int n=1; n<=N; ++n) {
         for(int k=L-2; k>=0; --k)
            for(int z=0; n-z-1>=1; z+=L)
               U[k][n] = (U[k][n] + A3[z]*U[k+1][n-z-1]) % MODVAL;
         for(int i=L; i<=n; i+=L)
            A4[n] = (A4[n] + 4*U[0][i]*A4[n-i]) % MODVAL;
         for(int i=L; i<=n; i+=L)
            A3[n] = (A3[n] + 3*U[0][i]*A3[n-i]) % MODVAL;
      }
      return int(A4[N]);
   }
};

文脈自由文法を定義する。簡単のためL=3、ぷよはabcの3色という例で。

• A =「全消しできる配ぷよ列」
• U =「最初のぷよが最後まで残るけど結局全消しできる配ぷよ列」

A ::= U*
U ::= a A[端!a] a A[端!a] a | b A[端!b] b A[端!b] b | c A[端!c] c A[端!c] c
A[端!a] ::= U[端!a]*
A[端!b] ::= U[端!b]*
A[端!c] ::= U[端!c]*
U[端!a] ::= b A[端!b] b A[端!b] b | c A[端!c] c A[端!c] c
U[端!b] ::= a A[端!c] a A[端!c] a | a A[端!a] a A[端!a] a
U[端!c] ::= c A[端!a] c A[端!a] c | b A[端!b] b A[端!b] b

これにマッチする長さNの文字列の個数、が求める物。