2018-2019 ICPC Asia Dhaka Regional H-Tile Game

問題のリンク

問題概要

N×Mのグリッドが与えられ、その内幾つかのマスに数字の書かれたタイルが置かれている。このグリッドに対して左詰め右詰め上詰め下詰めの操作を好きな順番で好きな回数行える。初期盤面は左下詰めで与えられる。左下詰めの盤面の状態で考えられる盤面の総数を で割った余りを求めよ。

制約

考察

数字を無視すると左下詰めの状態は一意。また一度行った操作を逆順に行うとまた同じ盤面に戻ることを考えると、初期状態から↑→↓←の順に(要は一周)操作していくものとしていいことが分かる。

ただ愚直に盤面を数え上げると当然間に合わない→周期性に注目

実験して見ると一部のマス同士でサイクルが出来ていることが分かるので、実際に1周させてみて、各サイクルの周期を調べる。これらのLCMが求める答え。

実装

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

const int N=210;
int n,m;
int a[N][N]; // 初期盤面
int b[4][N][N]; // 初期盤面に対してそれぞれ↑→↓←の操作を行った盤面
bool used[N*N];
char fi[N][N];
constexpr ll mod=78294349;

template<typename T>
map<T,ll> factorize(T x){
  map<T,ll> res;
  for(ll i=2;i*i<=x;i++){
    while(x%i==0){
      x/=i;
      res[i]++;
    }
  }
  if(x!=1)res[x]++;
  return res;
}

ll mod_pow(ll a,ll b){
  a%=mod;
  if(b==0)return 1;
  if(b==1)return a;
  ll res=mod_pow(a,b/2)%mod;
  res*=res; res%=mod;
  if(b%2)res*=a;
  return res%mod;
}

void up(int a[N][N],int b[N][N]){
  for(int i=0;i<m;i++){
    int now=0;
    for(int j=0;j<n;j++){
      if(a[j][i]){
        b[now][i]=a[j][i];
        now++;
      }
    }
  }
}

void right(int a[N][N],int b[N][N]){
  for(int i=0;i<n;i++){
    int now=m-1;
    for(int j=m-1;j>=0;j--){
      if(a[i][j]){
        b[i][now]=a[i][j];
        now--;
      }
    }
  }
}

void down(int a[N][N],int b[N][N]){
  for(int i=0;i<m;i++){
    int now=n-1;
    for(int j=n-1;j>=0;j--){
      if(a[j][i]){
        b[now][i]=a[j][i];
        now--;
      }
    }
  }
}

void left(int a[N][N],int b[N][N]){
  for(int i=0;i<n;i++){
    int now=0;
    for(int j=0;j<m;j++){
      if(a[i][j]){
        b[i][now]=a[i][j];
        now++;
      }
    }
  }
}

int main(){
  int q; cin >> q;
  for(int _=0;_<q;_++){
    cout << "Case " << _+1 << ": ";
    cin >> n >> m;
    ll res=1;
    int now=1;
    map<int,pair<int,int>> mp;
    for(int i=0;i<n;i++){
      for(int j=0;j<m;j++){
        cin >> fi[i][j];
        a[i][j]=0;
        for(int k=0;k<4;k++){
          b[k][i][j]=0;
        }
        if(fi[i][j]=='#'){
          a[i][j]=now;
          mp[now]=make_pair(i,j);
          now++;
        }
      }
    }
    // 回転のシミュレーション
    up(a,b[0]);
    right(b[0],b[1]);
    down(b[1],b[2]);
    left(b[2],b[3]);
    vector<int> v; // 各サイクルの周期
    for(int i=0;i<n*m+1;i++){
      used[i]=0;
    }
    for(int i=0;i<n;i++){
      for(int j=0;j<m;j++){
        if(a[i][j]){
          int now=a[i][j];
          int cnt=0;
          while(used[now]==0){
            used[now]=1;
            cnt++;
            int x=mp[now].first,y=mp[now].second;
            now=b[3][x][y];
          }
          if(cnt)v.push_back(cnt);
        }
      }
    }
    map<ll,ll> fac;
    for(ll pp:v){
      auto m=factorize(pp);
      for(auto ppp:m){
        if(fac[ppp.first]==0){
          fac[ppp.first]=ppp.second;
        }else{
          fac[ppp.first]=max(fac[ppp.first],ppp.second);
        }
      }
    }
    for(auto pp:fac){
      res*=mod_pow(pp.first,pp.second);
      res%=mod;
    }
    cout << res << endl;
  }
}