/*
    問長度為N的字符串(uppercase)中，至少有K個長度為M的回文串的個數(shù)
    N<=11 

    一開始我在那里dp推，發(fā)現(xiàn)有重復之類的東西不好搞
    看了Sevenkplus的，容斥，感覺好神奇
    
    最多有P = N - M + 1個回文串
    由于規(guī)模比較小，枚舉選出哪幾個作為回文串，使得至少有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要計算的次數(shù)就是先減去其余集合Ti在這部分算的次數(shù)（減完就為空了），再加上1
     即為 1 - 其余集合Ti在這部分算的次數(shù)
    用num[i]表示集合Ti需要算的次數(shù)，則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獨立變量的個數(shù)
    對Ti,求獨立變量的個數(shù)，可以先建圖（利用回文串兩端相等的性質），然后dfs算出連通塊的個數(shù)就是獨立變量的個數(shù)了
*/
#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];//記錄需要計算的次數(shù)
    
    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īng)算過的次數(shù)，然后這個地方就空了，
                                                //再加上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的回文串的個數(shù)
    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);
    }
};