cafelier@SRM

SRM452 500

あとで | 15:04 |

LayCurseさんの記録 と Petr のソースを参考にしながら…うーむ思いつける気がしない。

// mod 演算用ユーティリティ
LL MODVAL = 1000000007LL;
LL ADD(LL x, LL y) { return (x+y)%MODVAL; }
LL SUB(LL x, LL y) { return (x-y+MODVAL)%MODVAL; }
LL MUL(LL x, LL y) { return (x*y)%MODVAL; }
LL POW(LL x, LL e) {
   LL v = 1;
   for(;e;x=MUL(x,x),e>>=1)
      if(e&1)
         v = MUL(v, x);
   return v;
}

// 本体
class IOIString { public:
   string  s;
   LL nI, nQ;

   int countIOIs(vector <string> mask) 
   {
      s  = accumulate( mask.begin(), mask.end(), string("") );
      nI = count( s.begin(), s.end(), 'I' );
      nQ = count( s.begin(), s.end(), '?' );

      return SUB( POW(2,nQ), non_IOI() ); // IOIじゃないものを数えて引く
   }

   LL non_IOI()
   {
      LL ans = 0;
      if( nI == 0 ) ans = ADD(ans,  1); // #I == 0
      if( nI == 0 ) ans = ADD(ans, nQ); // #I == 1
      if( nI == 1 ) ans = ADD(ans,  1); // #I == 1
      for(int D=1; D<s.size(); D+=2)
         for(int S=0; S<D; ++S)
            ans = ADD(ans, non_IOI_2(S, D)); // #I >= 2
      return ans;
   }

   LL non_IOI_2( int S, int D )
   {
      string t;
      for(int i=S; i<s.size(); i+=D)
         t += s[i];

      // t 以外の部分は全部 'O' でないとダメ
      if( count(t.begin(), t.end(), 'I') < nI )
         return 0;

      // t は /O*II+O*/ にマッチしないとダメ。4状態のオートマトンでDP
      LL q0=1, q1=0, q2=0, q3=0;
      for(int i=0; i<t.size(); ++i)
      {
         LL p0 = (t[i]=='O' ?         q0 : t[i]=='I' ?          0 : q0);
         LL p1 = (t[i]=='O' ?          0 : t[i]=='I' ?         q0 : q0);
         LL p2 = (t[i]=='O' ?          0 : t[i]=='I' ? ADD(q1,q2) : ADD(q1,q2));
         LL p3 = (t[i]=='O' ? ADD(q2,q3) : t[i]=='I' ?          0 : ADD(q2,q3));
         q0=p0, q1=p1, q2=p2, q3=p3;
      }
      return ADD(q2, q3);
   }
};

• "IOIでない文字列"とはどんなものかを考える
  • Iが1個もない
  • Iが1個しかない
  • Iが2個以上の場合は…？
    • I O^奇数 I というパターンはない。そこでIOIが作れてしまう
    • なので O^* I O^2a I O^2b I O^2c ... I O^* という形しかない。(a,b,c,... >= 0)
    • ところが
    • I O^2a I O^2b I だと、両端のIの真ん中がOであってはいけないので、この時必ず a==b
    • というわけで
    • O* (I O^2a)+ I O*
    • というパターンだけが可能

• このパターンを全部数え上げる。
  • Iどうしの間隔 D=1,3,5,... でループ
    • 最初のIの位置(mod D) S=0,1,2,.,,,,D-1 でループ
      • それぞれの(S,D)でのパターン数をカウント。重複ないので足すだけ。
      • S+iD番目だけ取り出してきた文字列をtとすると、
        • t以外の文字は全て O
        • t自体は O*II...IIO*
      • となってないといけないけれど、この条件は O( |t| )でチェックできる
• 入力文字列長さを N とすると
• 一見３重ループなので O(N^3) にみえるけど
• S<D, O(|t|)<O(N/D) なので</li>
• 全体の計算量は O(N^2)