考えたこと
- 両端が同じ文字で間が偶数、両端が違う文字で間が奇数ならちゃんと埋めれば0にできて1パターンしかない
- これ以外の場合どうやっても+1は回避できない
- +1になるパターン数を求めて掛けていけばよさそう
- 実験したら(間の数+1)パターンになった
- MODを忘れずに掛けていったら通った
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
template<unsigned MOD>
class ModInt {
public:
unsigned x;
ModInt(): x(0) { }
ModInt(signed y) : x(y >= 0 ? y % MOD : MOD - (-y) % MOD) {}
unsigned get() const { return x; }
ModInt inv() const {
ll a = 1, p = x, e = MOD-2;
while(e > 0) {
if(e%2 == 0) {p = (p*p) % MOD; e /= 2;}
else {a = (a*p) % MOD; e--;}
}
a %= MOD;
return ModInt(a);
}
ModInt pow(ll e) {
ll a = 1, p = x;
while(e > 0) {
if(e%2 == 0) {p = (p*p) % MOD; e /= 2;}
else {a = (a*p) % MOD; e--;}
}
a %= MOD;
return ModInt(a);
}
ModInt pow2() {
ll a = 1, p = 2, e = x;
while(e > 0) {
if(e%2 == 0) {p = (p*p) % MOD; e /= 2;}
else {a = (a*p) % MOD; e--;}
}
a %= MOD;
return ModInt(a);
}
bool operator <(ModInt b) { return x < b.x; }
bool operator >(ModInt b) { return x > b.x; }
bool operator<=(ModInt b) { return x <= b.x; }
bool operator>=(ModInt b) { return x >= b.x; }
bool operator!=(ModInt b) { return x != b.x; }
bool operator==(ModInt b) { return x == b.x; }
ModInt operator++() { x++; return *this; }
ModInt operator--() { x--; return *this; }
ModInt &operator+=(ModInt that) {
x = ((ll)x+that.x)%MOD;
return *this;
}
ModInt &operator-=(ModInt that) {
x = ((((ll)x-that.x)%MOD)+MOD)%MOD;
return *this;
}
ModInt &operator*=(ModInt that) {
x = (ll)x * that.x % MOD;
return *this;
}
ModInt &operator/=(ModInt that) {
x = (ll)x * that.inv() % MOD;
return *this;
}
ModInt &operator%=(ModInt that) {
x = (ll)x % that.x;
return *this;
}
ModInt operator+(ModInt that)const{return ModInt(*this) += that;}
ModInt operator-(ModInt that)const{return ModInt(*this) -= that;}
ModInt operator*(ModInt that)const{return ModInt(*this) *= that;}
ModInt operator/(ModInt that)const{return ModInt(*this) /= that;}
ModInt operator%(ModInt that)const{return ModInt(*this) %= that;}
};
typedef ModInt<1000000007> mint;
ostream &operator<<(ostream& os, mint a) { return os << a.x; }
istream &operator>>(istream& is, mint &a) { return is >> a.x; }
class TaroFillingAStringDiv1 {
public:
int getNumber(int N, vector <int> pos, string val)
{
int n = pos.size();
pair<int, char> p[55];
REP(i, n) p[i] = {pos[i]-1, val[i]};
sort(p, p+n);
mint ret = 1;
FOR(i, 1, n) {
if((p[i].first - p[i-1].first - 1) % 2) {
if(p[i-1].second != p[i].second) {
ret *= (p[i].first - p[i-1].first);
}
} else {
if(p[i-1].second == p[i].second) {
ret *= (p[i].first - p[i-1].first);
}
}
}
return ret.x;
}
};