SRM496 Div2 Hard(1000) PalindromfulString

PalindromfulString

AABAACBD

のように、これまでに出ていない文字が出現するときは今までに出てきた文字の辞書順次の文字、という制約を加えると候補となる文字列の数は少ない。Palindromfullな文字列にk種類の文字が出てきているなら文字を置き換えて_nP_k個のpalindromfullな文字列が得られる。

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

int N, M, K;

long long perm( long long n, long long k )
{
    long long r = 1;
    for ( int i=0; i<k; i++ )
        r *= n-i;
    return r;
}

long long BT( string s )
{
    int n = (int)s.length();
    char d = 'A'-1;     //  使われている辞書順最大の文字
    for ( int i=0; i<n; i++ )
        d = max( d, s[i] );

    if ( n >= N )
    {
        int c = 0;
        for ( int i=0; i<=N-M; i++ )
        {
            int f = 1;
            for ( int j=0; j<M/2; j++ )
                if ( s[i+j] != s[i+M-j-1] )
                    f = 0;
            c += f;
        }
        if ( c >= K )
            return perm(26,d-'A'+1);
        else
            return 0;
    }

    long long ans = 0;

    for ( char c='A'; c<=d+1; c++ )
        ans += BT(s+c);

    return ans;
}

class PalindromfulString{public:
long long count( int N, int M, int K )
{
    ::N = N,  ::M = M,  ::K = K;
    return BT("");
}};