Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2057-d1a417df
この記事にトラックバックする(FC2ブログユーザー)

SRM521 DIV1 HARD - Chimney (この記事を編集する[管理者用])

Source

TopCoder SRM521 DIV1 HARD (1000pt)
Problem Statement

問題概要

n段 (10^18以下) の煙突を作る.
各段では,問題文のlayer1とlayer2を交互に現れる形で,レンガの数の合計は4n.
レンガを置くには,その下に位置するべき2つのレンガがすでに置かれていなければいけない.
1個ずつレンガを置いていって,煙突を完成させる方法は何通りあるか mod 1000000007 で求める問題.

解法

テトリスのように,1段に4つのレンガ揃ったら,その段が消えると思って,回転して得られる状態を同一視すると状態数は10パターンぐらいしかない.
後は,1個レンガを置く状態遷移の行列を作って,4n回レンガを置いた時に空状態になるパターン数を行列べき乗を使って求める.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long
#define M 1000000007

int node;
int state[1000];
int edge[1000][1000];
int rev[5555];

int get_minimum(int st){
  int i,j;
  int down, mid, up;
  int res = st, tmp;

  down = st%16; st /= 16;
  mid  = st%16; st /= 16;
  up   = st%16; st /= 16;

  if( down==15 ){
    return get_minimum(mid+up*16);
  }

  rep(i,4){
    tmp = 0;
    rep(j,4) if(down&1<<j) tmp |=     (1<<((i+j)%4));
    rep(j,4) if(mid &1<<j) tmp |=  16*(1<<((i+j)%4));
    rep(j,4) if(up  &1<<j) tmp |= 256*(1<<((i+j)%4));
    if(res > tmp) res = tmp;
  }

  return res;
}

int is_valid(int st){
  int i;
  int down, mid, up;

  down = st % 16; st /= 16;
  mid  = st % 16; st /= 16;
  up   = st % 16; st /= 16;

  rep(i,4) if(mid&1<<i){
    if( !(down&1<<i) ) return 0;
    if( !(down&1<<((i+3)%4)) ) return 0;
  }
  rep(i,4) if(up&1<<i){
    if( !(mid&1<<i) ) return 0;
    if( !(mid&1<<((i+3)%4)) ) return 0;
  }

  return 1;
}





typedef struct ll_matrix{
  int r,c;
  ll **data;
}llMatrix;

llMatrix newLLMatrix(int r,int c){
  int i; llMatrix res;
  res.r=r; res.c=c;
  res.data    = (ll**) malloc(r*sizeof(ll*));
  res.data[0] = (ll*) malloc(r*c*sizeof(ll));
  REP(i,1,r) res.data[i] = res.data[i-1]+c;
  return res;
}

void* setMemoryLLMatrix(llMatrix *a,int r,int c,void *WorkMemory){
  int i;
  a->r=r; a->c=c;
  a->data = (ll**)WorkMemory; WorkMemory = (void*)(a->data + r);
  rep(i,r){a->data[i] = (ll*)WorkMemory; WorkMemory = (void*) (a->data[i] + c);}
  return WorkMemory;
}

void deleteLLMatrix(llMatrix *a){
  free(a->data[0]); free(a->data);
}

void llMatrixSetZero(llMatrix *a){
  int i,j;
  rep(i,a->r) rep(j,a->c) a->data[i][j]=0;
}

void llMatrixSetIdentity(llMatrix *a){
  int i,mx;
  mx=a->r; if(mx>a->c) mx=a->c;
  llMatrixSetZero(a); rep(i,mx) a->data[i][i]=1;
}

void llMatrixMultipleMod(llMatrix *a,llMatrix *b,llMatrix *res,ll m){
  int i,j,k;
  llMatrixSetZero(res);
  rep(i,res->r) rep(k,b->r) if(a->data[i][k]) rep(j,res->c) {
    res->data[i][j]+=a->data[i][k]*b->data[k][j];
    if(res->data[i][j]>=m) res->data[i][j]%=m;
  }
}

void llMatrixPowerMod(llMatrix *a,llMatrix *res,ll k,ll m,void *WorkMemory){
  int i,j,n=a->r;
  llMatrix tmp1,tmp2;
  
  res->r=res->c=n;
  if(k==0){ llMatrixSetIdentity(res); return; }
  if(k==1){ rep(i,n)rep(j,n)res->data[i][j]=a->data[i][j]; return; }
  if(k==2){ llMatrixMultipleMod(a,a,res,m); return; }

  WorkMemory = setMemoryLLMatrix(&tmp1,n,n,WorkMemory);
  llMatrixPowerMod(a, &tmp1, k/2, m, WorkMemory);
  if(k%2==0) llMatrixMultipleMod(&tmp1,&tmp1,res,m);
  else {
    WorkMemory = setMemoryLLMatrix(&tmp2,n,n,WorkMemory);
    llMatrixMultipleMod(&tmp1,&tmp1,&tmp2,m);
    llMatrixMultipleMod(a,&tmp2,res,m);
  }
}




class Chimney {
public:
int countWays(ll n) {
  int i,j,k,nx;
  int res;
  void *mem = malloc(10000000);
  llMatrix mt = newLLMatrix(33,33);
  llMatrix pw = newLLMatrix(33,33);

  rep(i,5555) rev[i] = -1;

  node = 1;
  rep(i,1000) rep(j,1000) edge[i][j] = 0;

  state[0] = 0; rev[0] = 0;

  rep(i,node){
    k = state[i];
    rep(j,12) if(!(k&1<<j)){
      nx = (k | (1<<j));
//      printf("-- %d %d\n",k,nx);
      if(!is_valid(nx)) continue;
      nx = get_minimum(nx);
//      printf("++ %d %d\n",k,nx);
      if(rev[nx]==-1){
        state[node] = nx;
        rev[nx] = node++;
      }
      edge[i][rev[nx]]++;
    }
  }

  printf("node = %d\n",node);

  mt.r = mt.c = node;
  rep(i,node) rep(j,node) mt.data[i][j] = edge[i][j];
  llMatrixPowerMod(&mt,&pw,4*n,M,mem);

  res = pw.data[0][0];

  free(mem);
  deleteLLMatrix(&mt);
  deleteLLMatrix(&pw);
  
  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2057-d1a417df
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。