/*
    问长度为N的字符串(uppercase)中，至少有K个长度为M的回文串的个数
    N<=11 

    一开始我在那里dp推，发现有重复之类的东西不好搞
    看了Sevenkplus的，容斥，感觉好神奇
    
    最多有P = N - M + 1个回文串
    由于规模比较小，枚举选出哪几个作为回文串，使得至少有K个，令这个模式为Ti
    （如N = 3, M= 2 , K = 1 ，一个合法的模式为 010）
    则答案为|T0∪T1∪Tc|，这里就要用到容斥了
    = ∑|Ti|
      -∑|Ti∩Tj|
      +∑|Ti∩Tj∩Tk|
      
     直接套用的话复杂度为2^(2^P) ！！

     与平常的容斥有点不一样，这里存在很多“Tj包含于Ti”，即其交集就是子集了
     如011包含于010
     因为满足011的肯定满足010，所以011是010的子集，这里注意了！！二进制枚举Ti的超集Tj，是模式Ti的子集

     画个韦恩图，一个集合Tj要计算的次数就是先减去其余集合Ti在这部分算的次数（减完就为空了），再加上1
     即为 1 - 其余集合Ti在这部分算的次数
    用num[i]表示集合Ti需要算的次数，则num[i] = 1 - ∑num[ii]  ii为i的超集
    for(int j = i+1 ; j < (1<<P) ; j++)
    {
        if((j & i) == i)//j是i的子集
            num[j] -= num[i];
    }
    所以集合Ti对答案的贡献为 ans += num[i]*26^cnt
    O((2^p)^2)
    cnt为集合Ti独立变量的个数
    对Ti,求独立变量的个数，可以先建图（利用回文串两端相等的性质），然后dfs算出连通块的个数就是独立变量的个数了
*/
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

class PalindromfulString
{
public:

    bool vi[11];
    vector<int>E[11];
    int  num[1<<10];//记录需要计算的次数
    
    int bitCount(int n)
    {
        int cnt = 0;
        while(n)
        {
            if(n&1)cnt++;
            n>>=1;
        }
        return cnt;
    }
    long long ipow(int a , int n)
    {
        long long ans = 1;
        for(int i =  0; i < n ; i ++)
            ans *= a;
        return ans;
    }
    void dfs(int u)
    {
        vi[u] = true;
        for(int i = 0 ; i < E[u].size();  i++)
        {
            if(!vi[E[u][i]])
                dfs(E[u][i]);
        }
    }
    long long count(int N, int M, int K)
    {
        int P = N - M + 1;
        for(int i = 0 ; i < (1<<P) ; i++)//初始，合法的Ti其num[i]=1，否则为0
        {
            if(bitCount(i) >= K)num[i] = 1;
            else num[i] = 0;
        }
        long long ans = 0;
        for(int i = 0 ; i < (1<<P) ; i ++)
        {
            if(num[i] == 0)
                continue;
            for(int j = 0 ; j < N ; j ++)
            {
                E[j].clear();
            }
            for(int j = 0 ; j < P; j ++)
            {
                if(i & (1<<j))
                {
                    int L = j , R = j + M - 1;
                    while(L<R)
                    {
                        E[L].push_back(R);
                        E[R].push_back(L);
                        L++;
                        R--;
                    }
                }
            }
            memset(vi,0,sizeof(vi));
            int cnt = 0;//dfs出有多少个连通块，答案就是26^cnt
            for(int j = 0 ; j < N ; j ++)
                if(!vi[j])
                {
                    cnt++;
                    dfs(j);
                }
            ans += num[i]*ipow(26,cnt);
            for(int j = i+1 ; j < (1<<P) ; j++)//这里应认为j是i的子集
            {
                if((j & i) == i)
                    num[j] -= num[i];//减去各个i对j这个子集已经算过的次数，然后这个地方就空了，
                                                //再加上j本身初始的1就是答案了
            }
        }
        return ans;
    }
};
//
//int main()
//{
//    int n , m , k;
//    while(cin>>n>>m>>k)
//    {
//        PalindromfulString test;
//        cout<<test.count(n,m,k)<<endl;
//    }
//
//    return 0;
//}

以上的做法很快
另外的做法是枚举放了多少个字母，怎么放，然后判断是否可行，比较慢

/*
    问长度为N的字符串(uppercase)中，至少有K个长度为M的回文串的个数
    N<=11 

    N比较小，暴力枚举这些位置放了什么，然后判断是否满足条件
    dfs(str , cur , used)
    在前面cur个中放了used个字母
    if cur = N 
        if 满足条件 return A[used] //A[used]指排列A(26,used)
    else
        枚举cur放的字母0  used
    复杂度应该是O(MNN!)
*/

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>

using namespace std;

class PalindromfulString
{
public :

    long long A[12];
    int N,M,K;

    bool chk(string str)
    {
        int cnt = 0;
        for(int i = 0 ;  i + M -1 < N ; i ++)
        {
            int L = i , R = i + M - 1;
            bool ok = true;
            while(L < R)
            {
                if(str[L] != str[R])
                {
                    ok = false;
                    break;
                }
                L ++;
                R --;
            }
            if(ok)
                cnt++;
        }
        return cnt >= K;
    }

    long long dfs(string str ,int cur , int used)
    {
        if(cur == N)
        {
            return chk(str) ? A[used] : 0;
        }
        long long ans = 0;
        for(int i = 0 ; i < used ; i ++)
        {
            ans += dfs(str + (char)('A' + i) , cur + 1 , used);
        }
        ans += dfs(str + (char)('A'+used) , cur+1 , used+1);
        return ans;
    }

    long long count(int _N, int _M, int _K)
    {    
        N = _N;
        M = _M;
        K = _K;

        A[0] = 1;
        for(int i =  1; i <= N ; i ++)
        {
            A[i] = A[i-1] * (26-i+1);
        }
        return dfs("",0,0);
    }
};