提出 #54877506

---

ソースコード 拡げる

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#include <time.h> 
#include <math.h> 
using namespace std;
using namespace __gnu_pbds; 
#define ll long long
#define ull unsigned long long
#define endl "\n"
#define MOD 53473031747542373
// For multiset
#define ordered_set tree<pair<ll,ll>, null_type,less<pair<ll,ll>>, rb_tree_tag,tree_order_statistics_node_update> 
// For ordered set
// #define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
// order_of_key (k) : Number of items strictly smaller than k .
// find_by_order(k) : K-th element in a set (counting from zero).

long long nCR(ll n, ll r) {
    if(n==0){
        return 0;
    }
    if(n<r){
        return 0;
    }
    //https://stackoverflow.com/questions/11809502/which-is-better-way-to-calculate-ncr
    if(r > n - r) r = n - r; // because C(n, r) == C(n, n - r)
    long long ans = 1;
    ll i;

    for(i = 1; i <= r; i++) {
        ans *= n - r + i;
        ans /= i;
    }

    return ans;
}
ll powerMod(ll x, ll y, ll mod){
    ll res = 1;    
    x = x % mod; 
    while (y > 0){
        if (y & 1){
            res = ((res%mod)*(x%mod)) % mod;
        }
        y = y>>1;
        x = ((x%mod)*(x%mod)) % mod;
    }
    return res;
}
ll power(ll x, ll y){
    ll res = 1;    
    while (y > 0){
        if (y & 1){
            res = ((res)*(x));
        }
        y = y>>1;
        x = ((x)*(x));
    }
    return res;
}
 // Returns n^(-1) mod p
ll modInverse(ll n, ll mod) {
    return powerMod(n, mod-2, mod);
}
vector<ll>fact(1e6+1,1);
void precomputeFactorial(ll mod){
    fact[0]=1;
    for(ll i=1;i<=1000000;++i){
        fact[i]=(i%mod)*(fact[i-1]%mod);
        fact[i]%=mod;
    }
}
// Returns nCr % p using Fermat's little theorem.
ll nCrModPFermat(ll n, ll r, ll mod) {
    if(n<r){
        return 0;
    }
    if (r==0){
        return 1;
    }
    if(fact[2]==1){
        precomputeFactorial(mod);
    }
    return (fact[n]* modInverse(fact[r], mod) % mod * modInverse(fact[n-r], mod) % mod) % mod;
}
// https://codeforces.com/blog/entry/62393 http://xorshift.di.unimi.it/splitmix64.c
struct custom_hash { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM);}};
ll find(ll i,vector<ll>&parent){ if(parent[i]!=i){ return parent[i] = find(parent[i],parent); } return parent[i];}

void merge(ll a,ll b,vector<ll>&rank,vector<ll>&parent){
    ll x = find(a,parent);
    ll y = find(b,parent);
    if(x==y){
        return;
    }
    if(rank[x]>=rank[y]){
        parent[y]=x;
        // cout<<"rank[y] = "<<rank[]
        rank[x]+=rank[y];
        rank[y]=0;
    }
    else{
        parent[x]=y;
        rank[y]+=rank[x];
        rank[x]=0;
    }
}

vector<vector<ll>>dir={{0,-1},{0,1},{1,0},{-1,0}};
ll max(ll a,ll b){ return a>b?a:b;}
ll min(ll a,ll b){ return a<b?a:b;}
ll lcm(ll a,ll b){return a*b/__gcd(a,b);}
ll complement(ll x,ll n){ return (x^(n-1));}
bool checkPrime(ll num){for(ll i=2;i<=sqrt(num);++i){if(num%i==0){return false;}}return true;}
bool isSorted(vector<ll>&vect){for(ll i=1;i<vect.size();++i){if(vect[i]<vect[i-1]){return false;}}return true;}
bool isPowerOfTwo(ll num){return (num&(num-1))==0;}
template <typename T> bool allEqual(const std::vector<T>& vec) { if (vec.empty()) { return true; } T reference = vec[0]; for (size_t i = 1; i < vec.size(); ++i) { if (vec[i] != reference) { return false; }} return true;}


const char nl = '\n';
const char sp = ' ';
void yesno(bool a) { cout << (a ? "Yes\n" : "No\n"); }
template<typename L, typename R> ostream& operator<<(ostream& out, const pair<L, R>& p) { out << '(' << p.first << ',' << p.second << ')';return out;} 
template<typename T> ostream& operator<<(ostream& out, const vector<T>& v) { for (auto &i : v) out << i << ' '; out << nl; return out;}
template<typename T> ostream& operator<<(ostream& out, const set<T>& v) { for (auto &i : v) out << i << ' '; out << nl; return out;}
template<typename T> ostream& operator<<(ostream& out, const unordered_set<T>& v) { for (auto &i : v) out << i << ' '; out << nl; return out;}
template<typename T> ostream& operator<<(ostream& out, const unordered_set<T,custom_hash>& v) { for (auto &i : v) out << i << ' '; out << nl; return out;}
template<typename K, typename V> ostream& operator<<(ostream& out, const map<K, V>& m) { out << '['; for (auto &it : m) { out << it.first << ':' << it.second << sp;}out << "]\n";return out;}
template<typename K, typename V> ostream& operator<<(ostream& out, const unordered_map<K, V>& m) { out << '['; for (auto &it : m) { out << it.first << ':' << it.second << sp; }out << "]\n";return out;}
template<typename K, typename V> ostream& operator<<(ostream& out, const unordered_map<K, V,custom_hash>& m) { out << '['; for (auto &it : m) { out << it.first << ':' << it.second << sp; }out << "]\n";return out;}
void print(vector<ll>&arr,ll index=0){ for(ll i=index;i<arr.size();++i){ cout<<arr[i]<<" ";} cout<<endl;} 

class segmentTree{
    public:
    vector<ll>segTree;
    vector<ll>segArr;

    segmentTree(ll n){
        segArr.resize(n);
        segTree.resize(4*n);
    }   

    void build(ll node,ll start,ll end){
        if(start==end){
            segTree[node]=segArr[start];
            return;
        }
        ll mid = start+(end-start)/2;
        build(2*node,start,mid);
        build(2*node+1,mid+1,end);
        segTree[node]=max(segTree[2*node],segTree[2*node+1]);
    }

    ll query(ll node,ll start,ll end,ll l,ll r){
        if(l>end||r<start){
            return LONG_LONG_MIN;
        }
        if(l<=start&&r>=end){
            return segTree[node];
        }
        ll mid = start+(end-start)/2;
        auto p1 = query(2*node,start,mid,l,r);
        auto p2 = query(2*node+1,mid+1,end,l,r);
        return max(p1,p2);
    }

    void update(ll node,ll start,ll end,ll index,ll value){
        if(start==end){
            segArr[start]=value;
            segTree[node]=value;
            return;
        }
        ll mid = start+(end-start)/2;
        if(mid>=index){
            update(2*node,start,mid,index,value);
        }
        else{
            update(2*node+1,mid+1,end,index,value);
        }
        segTree[node]=max(segTree[2*node],segTree[2*node+1]);
    }
};

class LazySegTreeMaxMin {
    public:
    vector<ll>segTree;
    vector<ll>segArr;
    vector<ll>lazy;

    LazySegTreeMaxMin(ll n){
        segArr.resize(n);
        segTree.resize(4*n);
        lazy.resize(4*n);
    }  

    void push(ll node){
        lazy[2*node]+=lazy[node];
        lazy[2*node+1]+=lazy[node];
        segTree[2*node]+=lazy[node];
        segTree[2*node+1]+=lazy[node];
        lazy[node]=0;
    } 

    void build(ll node,ll start,ll end){
        if(start==end){
            segTree[node]=segArr[start];
            //cout<<"node = "<<node<<" for range = "<<start<<" "<<end<<endl;
            return;
        }
        ll mid = start+(end-start)/2;
        build(2*node,start,mid);
        build(2*node+1,mid+1,end);
        segTree[node]=max(segTree[2*node],segTree[2*node+1]);
        // cout<<"node = "<<node<<" for range = "<<start<<" "<<end<<endl;
    }

    ll query(ll node,ll start,ll end,ll l,ll r){
        if(l>end||r<start){
            return LONG_LONG_MIN;
        }
        if(l<=start&&r>=end){
            return segTree[node];
        }
        push(node);
        ll mid = start+(end-start)/2;
        auto p1 = query(2*node,start,mid,l,min(r,mid));
        auto p2 = query(2*node+1,mid+1,end,max(l,mid+1),r);
        return max(p1,p2);
    }

    void update(ll node,ll start,ll end,ll l,ll r,ll value){
        if(l>end||r<start){
            return;
        }
        if(l<=start&&r>=end){
            lazy[node]+=value;
            segTree[node]+=value;
        }
        else{
            push(node);
            ll mid = start+(end-start)/2;
            update(2*node,start,mid,l,min(r,mid),value);
            update(2*node+1,mid+1,end,max(l,mid+1),r,value);
            segTree[node]=max(segTree[2*node],segTree[2*node+1]);
        }
    }
};


class LazySegTreeSum {
    public:
    vector<vector<ll>>segTree;
    vector<vector<ll>>segArr;
    vector<vector<ll>>lazy;
    vector<ll>length;
    vector<ll>a;
    vector<ll>b;
    vector<ll>c;
    ll mod = 998244353;
    LazySegTreeSum(ll n){
        segArr=vector<vector<ll>>(n,vector<ll>(3));
        segTree=vector<vector<ll>>(4*n,vector<ll>(3));
        lazy=vector<vector<ll>>(4*n,vector<ll>(3));
        length = vector<ll>(4*n);
    }  

    void push(ll node,ll addA,ll addB){
        lazy[node][0]=(lazy[node][0]+addA)%mod;
        lazy[node][1]=(lazy[node][1]+addB)%mod;
        ll len = length[node];
        segTree[node][2]=(segTree[node][2]+(addA*segTree[node][1])%mod+(addB*segTree[node][0])%mod+addA*addB%mod*len)%mod;
        segTree[node][0]=(segTree[node][0]+addA*len)%mod;
        segTree[node][1]=(segTree[node][1]+addB*len)%mod;
    } 

    void down(ll node){
        push(2*node,lazy[node][0],lazy[node][1]);
        push(2*node+1,lazy[node][0],lazy[node][1]);
        lazy[node][0]=0;
        lazy[node][1]=0;
    }

    void build(ll node,ll start,ll end){
        length[node]=end-start+1;
        if(start==end){
            segTree[node][0]=a[start];
            segTree[node][1]=b[start];
            segTree[node][2]=c[start];
            //cout<<"node = "<<node<<" for range = "<<start<<" "<<end<<endl;
            return;
        }
        ll mid = start+(end-start)/2;
        build(2*node,start,mid);
        build(2*node+1,mid+1,end);
        for(ll j=0;j<=2;++j){   
            segTree[node][j]=segTree[2*node][j]+segTree[2*node+1][j];
            segTree[node][j]%=mod;
        }
        // cout<<"node = "<<node<<" for range = "<<start<<" "<<end<<endl;
    }

    ll query(ll node,ll start,ll end,ll l,ll r){
        if(l>r){
            return 0;
        }
        if(l<=start&&r>=end){
            return segTree[node][2]%mod;
        }
        down(node);
        ll mid = start+(end-start)/2;
        ll p1 = query(2*node,start,mid,l,min(r,mid));
        ll p2 = query(2*node+1,mid+1,end,max(l,mid+1),r);
        return ((p1%mod)+(p2%mod))%mod;
    }

    void update(ll node,ll start,ll end,ll l,ll r,ll pos,ll value){
        if(l>r){
            return;
        }
        if(l<=start&&r>=end){
            // cout<<"start = "<<start<<" end = "<<end<<endl;
            push(node,!pos?value:0,pos?value:0);
        }
        else{
            down(node);
            ll mid = start+(end-start)/2;
            update(2*node,start,mid,l,min(r,mid),pos,value);
            update(2*node+1,mid+1,end,max(l,mid+1),r,pos,value);
            // cout<<"Here, start = "<<start<<" end = "<<end<<endl;
            // ll originalVal = segTree[node][pos];
            segTree[node][pos]=segTree[2*node][pos]+segTree[2*node+1][pos];
            segTree[node][pos]%=mod;
            segTree[node][1-pos]=segTree[2*node][1-pos]+segTree[2*node+1][1-pos];
            segTree[node][1-pos]%=mod;
            segTree[node][2]=segTree[2*node][2]+segTree[2*node+1][2]; 
            segTree[node][2]%=mod;
        }
    }
};

struct two_sat {
    ll n;
    vector<vector<ll>> g, gr;
    vector<ll> comp, topological_order, answer;
    vector<bool> vis;

    two_sat() {}

    two_sat(ll _n) { init(_n); }

    void init(ll _n) {
        n = _n;
        g.assign(2 * n+5, vector<ll>());
        gr.assign(2 * n+5, vector<ll>());
        comp.resize(2 * n+5);
        vis.resize(2 * n+5);
        answer.resize(2 * n+5);
    }

    void add_edge(ll u, ll v) {
        g[u].push_back(v);
        gr[v].push_back(u);
    }

    // At least one of them is true
    void add_clause_or(ll i, bool f, ll j, bool g) {
        add_edge(i + (f ? n : 0), j + (g ? 0 : n));
        add_edge(j + (g ? n : 0), i + (f ? 0 : n));
    }

    // Only one of them is true
    void add_clause_xor(ll i, bool f, ll j, bool g) {
        add_clause_or(i, f, j, g);
        add_clause_or(i, !f, j, !g);
    }

    // Both of them have the same value
    void add_clause_and(ll i, bool f, ll j, bool g) {
        add_clause_xor(i, !f, j, g);
    }

    void dfs(ll u) {
        vis[u] = true;
        for (const auto &v : g[u])
            if (!vis[v]) dfs(v);
        topological_order.push_back(u);
    }

    void scc(ll u, ll id) {
        vis[u] = true;
        comp[u] = id;
        for (const auto &v : gr[u])
            if (!vis[v]) scc(v, id);
    }

    bool satisfiable() {
        fill(vis.begin(), vis.end(), false);

        for (ll i = 1; i <= 2 * n; i++)
            if (!vis[i]) dfs(i);

        fill(vis.begin(), vis.end(), false);
        reverse(topological_order.begin(), topological_order.end());

        ll id = 0;
        for (const auto &v : topological_order)
            if (!vis[v]) scc(v, id++);

        for (ll i = 1; i <= n; i++) {
            if (comp[i] == comp[i + n]) return false;
            answer[i] = (comp[i] > comp[i + n] ? 1 : 0);
        }
        return true;
    }
};

// unordered_map<ll,ll,custom_hash>compressedCoordinate;
// ll max_coord=0;
// void coordinateCompression(vector<ll>&arr){
//     vector<ll>temp = arr;
//     ll _id = 1;
//     sort(temp.begin(),temp.end());
//     for(auto &elem:temp){
//         if(!compressedCoordinate.count(elem)){
//             compressedCoordinate[elem]=_id;
//             max_coord = max(max_coord,_id);
//             _id++;
//         }
//     }
// }

// vector<ll> manacher_odd(string &s){
//     ll n = s.length();
//     s = "$"+s+"^";
//     vector<ll>p(n+2);
//     ll l=1,r=1;
//     for(ll i=1;i<=n;++i){
//         p[i]=max(0,min(r-i,p[l+(r-i)]));
//         while(s[i-p[i]]==s[i+p[i]]){
//             p[i]++;
//         }
//         if(i+p[i]>r){
//             l = i-p[i];
//             r = i+p[i];
//         }
//     }
//     return {p.begin()+1,p.end()-1};
// }

// vector<ll> manacher(string s) {
//     string str;
//     for(auto &ch:s){
//         str.push_back('#');
//         str.push_back(ch);
//     }
//     str.push_back('#');
//     vector<ll>arr = manacher_odd(str);
//     return {arr.begin()+1,arr.end()-1};
// }
ll mod = 998244353;
unordered_map<char,ll>mp={{'A',0},{'B',1}};
ll K;
bool isPalindrome(ll currMask){
    ll start = 0;
    ll end = K-1;
    while(start<end){
        if((currMask&(1<<start))&&(currMask&(1<<end))){
            start++;
            end--;
        }
        else if(!(currMask&(1<<start))&&!(currMask&(1<<end))){
            start++;
            end--;
        }
        else{
            return false;
        }
    }
    return true;
}
ll dp[1001][(1<<10)+9];
ll helper(ll idx,ll n,string &str,ll k,ll mask){
    if(idx>=n){
        if(isPalindrome(mask)){
            return 0;
        }
        return 1;
    }
    if(idx>=k&&isPalindrome(mask)){
        return 0;
    }
    if(dp[idx][mask]!=-1){
        return dp[idx][mask];
    }
    ll pos = (idx<=k-1)?k-1-idx:0;
    ll superMask = (1<<k)-1;
    ll currMask = (idx<=k-1)?mask:(mask<<1)&superMask;
    ll newMask;
    ll ans = 0;
    // cout<<"Initially "<<endl;
    if(str[idx]=='?'){
        newMask=currMask|(mp['B'])<<pos;
        ans+=helper(idx+1,n,str,k,newMask);
        ans%=mod;
        newMask=currMask|(mp['A'])<<pos;
        ans+=helper(idx+1,n,str,k,newMask);
        ans%=mod;
    }
    else{
        newMask=currMask|(mp[str[idx]])<<pos;
        ans+=helper(idx+1,n,str,k,newMask);
        ans%=mod;
    }
    return dp[idx][mask]=ans%mod;
}
void solve(bool printTestcase){
    ll n,k;
    cin>>n>>k;
    K = k;
    string str;
    cin>>str;
    memset(dp,-1,sizeof(dp));
    cout<<helper(0,n,str,k,0)<<endl;
}   

int main() {
    cout.precision(10); cout.setf(ios::fixed);
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    cout.tie(NULL);
    #ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif
    ll t=1;
    // cin>>t;
    for(ll i=1;i<=t;++i){
        solve(false);
    }
}

提出情報

コンパイルエラー

Main.cpp: In function ‘bool isSorted(std::vector<long long int>&)’:
Main.cpp:115:44: warning: comparison of integer expressions of different signedness: ‘long long int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  115 | bool isSorted(vector<ll>&vect){for(ll i=1;i<vect.size();++i){if(vect[i]<vect[i-1]){return false;}}return true;}
      |                                           ~^~~~~~~~~~~~
Main.cpp: In function ‘void print(std::vector<long long int>&, long long int)’:
Main.cpp:131:56: warning: comparison of integer expressions of different signedness: ‘long long int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  131 | void print(vector<ll>&arr,ll index=0){ for(ll i=index;i<arr.size();++i){ cout<<arr[i]<<" ";} cout<<endl;}
      |                                                       ~^~~~~~~~~~~
Main.cpp: In function ‘void solve(bool)’:
Main.cpp:516:17: warning: unused parameter ‘printTestcase’ [-Wunused-parameter]
  516 | void solve(bool printTestcase){
      |            ~~~~~^~~~~~~~~~~~~

ジャッジ結果