# Untitled

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>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;
}```