SRM541 Div1 Medium(550) AkariDaisukiDiv1

AkariDaisukiDiv1

3通りの場合に分けて考える。f^k(S)が短い間は、そのまま計算すれば良い。f^k(S)が長くなったら、文字列の連結によってf^k(S)の中央に新たにFが現われることは無くなるので、接頭辞と接尾辞のみを覚えておいて計算する。kが大きくなると、C(k)をf^k(S)が含むFの個数として、C(i)-2*C(i-1)が一定となるので、数字の計算だけで答えが求められる。

#include <string>
#include <vector>
using namespace std;

string f( string Waai, string Akari, string Daisuki, string X )
{
    return Waai + X + Akari + X + Daisuki;
}

int count( string S, string F )
{
    int c = 0;
    for ( int i=0; i<(int)S.size()-(int)F.size()+1; i++ )
        if ( S.substr(i,F.size())==F )
            c++;
    return c;
}

class AkariDaisukiDiv1{public:
int countF( string Waai, string Akari, string Daisuki, string S, string F, int k )
{
    long long M = 1000000007;

    //  C[i]: f^i(S)が含むFの個数
    vector<int> C(1,count(S,F));

    //  ナイーブに計算
    int i=1;
    for ( ; (int)S.length()<1000; i++ )
    {
        S = f(Waai,Akari,Daisuki,S);
        C.push_back(count(S,F));
    }

    //  接頭辞と接尾辞のみを保持して計算
    string pref = S.substr(0,100);
    string suff = S.substr(S.length()-100);

    int d = 0;      //  Fの出現回数の増分

    for ( ; i<1000; i++ )
    {
        d = 0;
        
        //  Waai X が含みXが含まない、Fの個数
        string t = Waai+pref;
        for ( int j=0; j<(int)Waai.length(); j++ )
            if ( t.substr(j,F.length())==F )
                d++;
        //  X Akari X が含みXが含まない、Fの個数
        t = suff + Akari + pref;
        for ( int j=(int)(suff.length()-F.length()+1);
              j<(int)(suff.length()+Akari.length()); j++ )
            if ( t.substr(j,F.length())==F )
                d++;

        //  X Daisuki が含みXが含まない、Fの個数
        t = suff + Daisuki;
        for ( int j=(int)(suff.length()-F.length()+1);
              j<(int)(suff.length()+Daisuki.length()-F.length()+1); j++ )
            if ( t.substr(j,F.length())==F )
                d++;

        C.push_back((C[i-1]*2+d)%M);

        pref = (Waai+pref).substr(0,100);
        suff = (suff+Daisuki).substr(suff.length()+Daisuki.length()-100);
    }
    
    if ( (int)C.size()>=k+1 )
    {
        return C[k];
    }
    else
    {
        long long c = C[i-1];
        for ( ; i<=k; i++ )
            c = (c*2+d)%M;
        return (int)c;
    }

}};