Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
3.9 kB
2
Indexable
Never

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define lol long long
#define all(x) x.begin(),x.end()
#define rev(x) x.rbegin(),x.rend()
#define nline "\n"
#define ppi pair<int,int>
#define lol long long
#define hell 1000000007
#define ll long long
#define ld long double
#define pb push_back
#define coutyes cout << "YES" << endl
#define coutno cout << "NO" << endl
#define endl '\n'
#define ff first
#define ss second
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);

//2d prefix{
    //to cal prefix ->pre[i][j]= v[i][j]+pre[i][j-1]+pre[i-1][j]-pre[i-1][j-1];
    //to get ans from a,b->c,d ->pre[c][d]-pre[a-1][d]-pre[c][b-1]+pre[a-1][b-1];
//}

vector<lol>adj[200001];
vector<lol>vis;
vector<lol>parent;

bool prime(int n) {
if (n < 2) return false;
for (int x = 2; x*x <= n; x++) {
if (n%x == 0) return false;
}
return true;
}

vector<lol> factors(lol n) {
vector<lol> f;
for (lol x = 2; x*x <= n; x++) {
while (n%x == 0) {
f.push_back(x);
n /= x;
}
}
if (n > 1) f.push_back(n);
return f;
}


long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

class DisjointSet{
    vector<ll>rank,parent,size;
public:
    DisjointSet(int n){
        rank.resize(n+1,0);
        parent.resize(n+1);
        size.resize(n+1);
        for(int i=0; i<=n; i++){
            parent[i]=i;
            size[i]=1;
        }
    }

    int findUPar(int node){
        if(node==parent[node]) return node;

        return parent[node]=findUPar(parent[node]);
    }

    void unionbyrank (int u, int v){
        int rootx = findUPar(u);
        int rooty = findUPar(v);
        if(rank[rooty]<rank[rootx]){
            parent[rooty]=rootx;
        }
        else if(rank[rootx]<rank[rooty]){
            parent[rootx]=rooty;
        }
        else {
            parent[rootx]=rooty;
            rank[rooty]++;
        }
    }
    
    void unionBySize(int u, int v){
        int rootx = findUPar(u);
        int rooty = findUPar(v);
        if(rootx==rooty) return;
        if(size[rootx]<size[rooty]){
            parent[rootx]=rooty;
            size[rooty]+=size[rootx];
        }
        else{
            parent[rooty]=rootx;
            size[rootx]+=size[rooty];
        }
    }
};

map<pair<lol,string>,lol>mp;
lol rec(lol i,string temp,string &s,lol k){

    // if(i>=k) cout<<temp.size()<<endl;
    if(i==s.size()){
        string x = temp;
        reverse(all(x));
      if(x==temp) return 0;
      else  return 1;
    }
    if(mp.find({i,temp})!=mp.end()) return mp[{i,temp}];
    lol ans = 0;
    if(i>=(k)){
        string z = temp;
        reverse(all(z));
        if(z==temp){ans= 0;}
        else{
            
            
            temp.erase(temp.begin());
            string one=temp,two=temp,three=temp;
            one+='A';two+='B';three+=s[i];
             if(s[i]=='?'){
           
           ans = rec(i+1,one,s,k)+rec(i+1,two,s,k);
        }
        else ans= rec(i+1,three,s,k);

        }
    }
    else{
         string one=temp,two=temp,three=temp;
            one+='A';two+='B';three+=s[i];
             if(s[i]=='?'){
           
           ans = rec(i+1,one,s,k)+rec(i+1,two,s,k);
        }
        else ans= rec(i+1,three,s,k);
    }
    return mp[{i,temp}]=ans;
}


void solve(){
    
    lol n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    cout<<rec(0,"",s,k)<<endl;;
    cout<<mp.size()<<endl;
}


int main(){
    IOS;
    int t=1;
    // cin>>t;
    while(t-->0){

    solve();
    }
    

    return 0;
}
Leave a Comment