Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

January 2011 Challenge 2問目 - Chess Pushing Game (この記事を編集する[管理者用])

Source

codechef January 2011 Challenge 2問目
Problem Statement
January 2011 Challengeの参加記録

問題概要

3列の半無限のチェス盤の端に,1列に1つのコマが置いてある.
各ターン,1つのコマを選んで1マス進む.
1つ目のコマは2つ目のコマより先に行くことができず,2つ目のコマは3つ目のコマより先に行くことができない.
2つ目のコマは1つ目のコマよりDマス (7以下) より先に行くことはできず,3つ目のコマは2つ目のコマよりDマスより先に行くことはできない.
Kターン後 (10^9以下) に同じ場所に3つのコマがいるとき,そのような移動方法は何通りあるか mod 1000000007 で求める問題.

解法

状態遷移を行列で書き下して,行列べき乗.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

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,int 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);
  }
}


#define M 1000000007

int main(){
  int i,j,k,a,b;
  int inv[8][8], rev[80][2], sz;
  int D, K;
  llMatrix mt, pw;
  void *mem;

  scanf("%d%d",&D,&K);
  if(!K) {puts("1"); return 0;}
  if(K%3){puts("0"); return 0;}
  if(!D) {puts("0"); return 0;}

  sz = 0;
  rep(i,D+1) rep(j,D+1){
    inv[i][j] = sz;
    rev[sz][0] = i; rev[sz][1] = j;
    sz++;
  }

  mt = newLLMatrix(sz,sz);
  pw = newLLMatrix(sz,sz);
  mem = (void*)malloc(7000000);

  rep(i,sz) rep(j,sz) mt.data[i][j] = 0;
  rep(i,sz){
    a = rev[i][0]; b = rev[i][1];
    if(a)           mt.data[i][inv[a-1][b  ]]++;
    if(a+1<=D && b) mt.data[i][inv[a+1][b-1]]++;
    if(b+1<=D)      mt.data[i][inv[a  ][b+1]]++;
  }

  llMatrixPowerMod(&mt,&pw,K,M,mem);
  printf("%lld\n",pw.data[0][0]);

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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