結果
| 問題 |
No.1766 Tatsujin Remix
|
| コンテスト | |
| ユーザー |
 riano
|
| 提出日時 | 2021-11-26 22:45:52 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 13 ms / 2,000 ms |
| コード長 | 7,266 bytes |
| コンパイル時間 | 1,652 ms |
| コンパイル使用メモリ | 175,848 KB |
| 実行使用メモリ | 9,088 KB |
| 最終ジャッジ日時 | 2024-06-29 18:18:56 |
| 合計ジャッジ時間 | 2,660 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 22 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define rrep2(i,n,k) for(int i=n-1;i>=n-k;i--)
#define vll(n,i) vector<long long>(n,i)
#define v2ll(n,m,i) vector<vector<long long>>(n,vll(m,i))
#define v3ll(n,m,k,i) vector<vector<vector<long long>>>(n,v2ll(m,k,i))
#define v4ll(n,m,k,l,i) vector<vector<vector<vector<long long>>>>(n,v3ll(m,k,l,i))
#define all(v) v.begin(),v.end()
#define chmin(k,m) k = min(k,m)
#define chmax(k,m) k = max(k,m)
#define Pr pair<ll,ll>
#define Tp tuple<int,int,int>
#define riano_ std::ios::sync_with_stdio(false);std::cin.tie(nullptr)
using Graph = vector<vector<int>>;
const ll mod = 998244353;
template<uint64_t mod>
struct modint{
uint64_t val;
constexpr modint(const int64_t val_=0) noexcept:val((val_%int64_t(mod)+int64_t(mod))%int64_t(mod)){}
constexpr modint operator-() const noexcept{
return modint(*this)=mod-val;
}
constexpr modint operator+(const modint rhs) const noexcept{
return modint(*this)+=rhs;
}
constexpr modint operator-(const modint rhs) const noexcept{
return modint(*this)-=rhs;
}
constexpr modint operator*(const modint rhs) const noexcept{
return modint(*this)*=rhs;
}
constexpr modint operator/(const modint rhs) const noexcept{
return modint(*this)/=rhs;
}
constexpr modint &operator+=(const modint rhs) noexcept{
val+=rhs.val;
val-=((val>=mod)?mod:0);
return (*this);
}
constexpr modint &operator-=(const modint rhs) noexcept{
val+=((val<rhs.val)?mod:0);
val-=rhs.val;
return (*this);
}
constexpr modint &operator*=(const modint rhs) noexcept{
val=val*rhs.val%mod;
return (*this);
}
constexpr modint &operator/=(modint rhs) noexcept{
uint64_t ex=mod-2;
modint now=1;
while(ex){
now*=((ex&1)?rhs:1);
rhs*=rhs,ex>>=1;
}
return (*this)*=now;
}
modint & operator++(){
val++;
if (val == mod) val = 0;
return *this;
}
modint operator++(int){
modint<mod> res = *this;
++*this;
return res;
}
constexpr bool operator==(const modint rhs) noexcept{
return val==rhs.val;
}
constexpr bool operator!=(const modint rhs) noexcept{
return val!=rhs.val;
}
friend constexpr ostream &operator<<(ostream& os,const modint x) noexcept{
return os<<(x.val);
}
friend constexpr istream &operator>>(istream& is,modint& x) noexcept{
uint64_t t;
is>>t,x=t;
return is;
}
};
typedef modint<mod> mint;
mint pw(long long a,long long b,long long m = mod){
if(a%m==0) return mint(0);
if(b==0) return mint(1);
else if(b%2==0){
long long x = pw(a,b/2,m).val;
return mint(x*x);
}
else{
long long x = pw(a,b-1,m).val;
return mint(a*x);
}
}
mint modinv(long long a, long long m = mod) {
long long b = m, u = 1, v = 0;
while (b) {
long long t = a / b;
a -= t * b; swap(a, b);
u -= t * v; swap(u, v);
}
u %= m;
return mint(u);
}
#define vm(n,i) vector<mint>(n,i)
#define v2m(n,m,i) vector<vector<mint>>(n,vm(m,i))
#define v3m(n,m,k,i) vector<vector<vector<mint>>>(n,v2m(m,k,i))
#define v4m(n,m,k,l,i) vector<vector<vector<vector<mint>>>>(n,v3m(m,k,l,i))
//binary trie (dynamic segtree version)
class binary_trie {
public:
ll n; ll len;
vector<vector<int>> to;
vector<int> content;
vector<int> count;
//vector<ll> sum;
//vector<ll> lis;
vector<int> emp = {-1,-1};
binary_trie(ll k){
n = 1;
len = k;
to.push_back(emp);
content.push_back(0);
count.push_back(0);
//sum.push_back(0);
}
//0-1のvectorに変換
vector<int> convert(ll x){
vector<int> c;
for(int i=0;i<=len;i++){
c.push_back(x%2); x /= 2;
}
return c;
}
mint size(void){
return count[0];
}
//xを追加する 既に存在していたらtrue
bool insert(ll x,int cc = 1){
bool ex = true;
auto p = convert(x);
int now = 0; count[now] += cc; //sum[now] += mint(x)*cc;
for(int i=len-1;i>=0;i--){
bool found = false;
if(to[now][p[i]]!=-1){
found = true;
now = to[now][p[i]]; count[now] += cc; //sum[now] += mint(x)*cc;
}
if(found) continue;
ex = false;
to[now][p[i]] = n;
to.push_back(emp);
content.push_back(p[i]);
count.push_back(cc);
//sum.push_back(mint(x)*cc);
now = n;
n++;
}
return ex;
}
//k以下の数の個数
int count_under(int k){
insert(k,0);
auto p = convert(k);
int now = 0; int res = 0;
for(int i=len-1;i>=0;i--){
if(p[i]==1&&to[now][0]!=-1){
res += count[to[now][0]];
}
now = to[now][p[i]];
}
res += count[now];
return res;
}
int binary_src(int k){
auto p = convert(k);
int now = 0; int res = 0;
int num = 0;
for(int i=len-1;i>=0;i--){
//cout << now << endl;
if(i==0){
res += count[now];
if(num-res==k){
return num;
}
else if(num-res==k-1){
return num+1;
}
}
else if(to[now][0]==-1){
if(res+num+(1LL<<(i-1))-1>=k){
return k-res;
}
else if(to[now][1]!=-1){
now = to[now][1]; continue;
}
else{
return k-(res+count[to[now][0]]);
}
}
else{
if(res+num+(1LL<<(i-1))-1+count[to[now][0]]>=k){
now = to[now][0];
}
else{
if(to[now][1]!=-1){
res += count[to[now][0]];
num += (1LL<<(i-1));
now = to[now][1];
}
else{
return k-(res+count[to[now][0]]);
}
}
}
}
return res;
}
};
int main() {
riano_; mint ans = 0;
ll N; cin >> N;
string S;
rep(i,N){
string s; cin >> s; S += s;
}
S += '.';
auto dp = v2m(N*8+1,2,0);
dp[0][0] = 1;
rep(i,N*8){
if(S[2*i]=='.'&&S[2*i+1]=='.'){
dp[i+1][0] += dp[i][0];
}
if(S[2*i+1]=='.'){
mint c = 1;
if(S[2*i]=='.') c *= 2;
dp[i+1][0] += c*(dp[i][0]+dp[i][1]);
}
mint c2 = 1;
if(S[2*i]=='.'){
if(S[2*i+1]=='.') c2 *= 2;
}
if(S[2*i+1]=='.'){
if(S[2*i+2]=='.') c2 *= 2;
}
dp[i+1][1] += c2*(dp[i][0]+dp[i][1]);
}
ans = dp[N*8][0] + dp[N*8][1];
cout << ans << endl;
}