Submission #2958129

Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define NDEBUG
#ifdef DEBUG
#include "../cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair


ll gcd(ll a, ll b) { while(a) swap(a, b%=a); return b; }

const ll MOD=1000000007LL;

#if 1
ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }
// ll comb(ll n, ll k) { ll v=1; for(ll i=1; i<=k; i++) v = DIV(MUL(v, n-i+1),i); return v; }
//
#else
ll ADD(ll x,ll y) { return x+y; }
ll MUL(ll x,ll y) { return x*y; }
#endif

ll solve(string& s) {
    int L = s.size();
    vector<ll> dp(4, 0LL);
    dp[3] = 1;
    rep(i,L){
        vector<ll> dp2(4, 0LL);
        switch (s[i]) {
            case 'A':
                dp2[0] = dp[0];
                dp2[1] = dp[1];
                dp2[2] = dp[2];
                dp2[3] = dp[3];

                dp2[0] = ADD(dp2[0], dp[3]);
                break;
            case 'B':
                dp2[0] = dp[0];
                dp2[1] = dp[1];
                dp2[2] = dp[2];
                dp2[3] = dp[3];

                dp2[1] = ADD(dp2[1], dp[0]);
                break;
            case 'C':
                dp2[0] = dp[0];
                dp2[1] = dp[1];
                dp2[2] = dp[2];
                dp2[3] = dp[3];

                dp2[2] = ADD(dp2[2], dp[1]);
                break;
            case '?':
                dp2[0] = MUL(dp[0], 3);
                dp2[1] = MUL(dp[1], 3);
                dp2[2] = MUL(dp[2], 3);
                dp2[3] = MUL(dp[3], 3);

                dp2[0] = ADD(dp2[0], dp[3]);
                dp2[1] = ADD(dp2[1], dp[0]);
                dp2[2] = ADD(dp2[2], dp[1]);
                break;
        }
        dp = dp2;
    }
    return dp[2];
}

int main() {
    string s; cin >> s;
    cout << solve(s) << endl;
    return 0;
}

Submission Info

Submission Time
Task D - We Love ABC
User naoya_t
Language C++14 (GCC 5.4.1)
Score 400
Code Size 3149 Byte
Status
Exec Time 9 ms
Memory 512 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 a01, a02, a03
All 400 / 400 a01, a02, a03, b04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23
Case Name Status Exec Time Memory
a01 1 ms 256 KB
a02 1 ms 256 KB
a03 1 ms 256 KB
b04 1 ms 256 KB
b05 1 ms 256 KB
b06 1 ms 256 KB
b07 1 ms 256 KB
b08 1 ms 256 KB
b09 1 ms 256 KB
b10 8 ms 512 KB
b11 9 ms 512 KB
b12 8 ms 512 KB
b13 8 ms 512 KB
b14 8 ms 512 KB
b15 8 ms 512 KB
b16 8 ms 512 KB
b17 8 ms 512 KB
b18 2 ms 256 KB
b19 1 ms 256 KB
b20 3 ms 256 KB
b21 9 ms 512 KB
b22 9 ms 512 KB
b23 9 ms 512 KB