AtCoder Regular Contest #025 D問題 - コンセント

Source

AtCoder Regular Contest #025
問題文

問題概要

縦に $H$ 列,横に $W$ 行の,$H \times W$ 個の穴が開いた壁がある.
縦,または,横に連続した $2$ つの穴にプラグを差し込むことでコンセントとして利用できる.
最初,全ての穴は塞がっていないとして,$N$ 日間以下のことを行う.
$k$ 日目では,$S_k$ 行 $T_k$ 列の穴が塞がってなければ塞ぎ,塞がっていれば塞がっていない状態にする.
$N$ 日間,それぞれの後に,コンセントの利用方法(プラグをいくつ差し込んでも良いとして差し込み方)は何通りあるかを ${\rm mod}\ 1000000007\ (10^9+7)$ で求める問題.

解法

まず最初の段階で,何通りの利用方法があるかを求める方法を考える.
状態を(今見ている列,今見ている列の中でどの穴が塞がっているか)を取りDPする.
各DPの状態遷移は,今見ている列のみ,または,今見ている列と次の列を使うプラブの差し込み方を全通り試す.
ここで,どの穴が塞がっているかの $2^H$ 通りの状態を $2^H$ 要素のベクトル $x_k$ と思うことで,DPの漸化式は $x_k = A x_{k-1}$ の形で書ける.
そこで,行列べき乗でパターンの数を計算できることになる.($x_n = A^n x_0$ のように計算する)
元々の問題に戻ると,穴が塞がっている場所は,遷移行列の形が変わることになる.
そこで,そこの行列を別処理してそこまでは行列べき乗で計算することを考える.(塞がっている列が $1$ 列なら $x_n = A^k B A^{N-1-k} x_n$ のように計算する)
穴が塞がる可能性のある列は $N$ 列しかないので,その他の連続する部分はひとまとめにしておき行列のべき乗は求めておく.
後は,穴が塞がる可能性のある列の,遷移行列を変更したり,全体の行列の積を求めたりできれば良い.
これは,各要素として遷移行列を持つsegment treeや,平方分割などを利用すれば良い.
$N+1$ 列目は塞がった穴が並んでいると思うと実装しやすい(かもしれない).
時間計算量はsegment treeを用いた場合で $O((2^H)^3 N \log N)$ 程度.

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

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

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long
#define MD 1000000007

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void writer(int x, char c){int i,sz=0,m=0;char buf[10];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}

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


int N;
ll X, Y, x[25000], y[25000];

int num;
llMatrix val[41000];
llMatrix mul[200000];
void *mem;

void init(int node, int left, int right){
  int i, j;
  int n1 = node * 2 + 1, n2 = node * 2 + 2, sz = right - left;

  if(sz==1){
    rep(i,1<<X) rep(j,1<<X) mul[node].data[i][j] = val[left].data[i][j];
    return;
  }

  init(n1, left, left+sz/2);
  init(n2, left+sz/2, right);
  llMatrixMultipleMod(&mul[n2], &mul[n1], &mul[node], MD);

//  printf("node %d\n",node);
//  rep(i,1<<X){ rep(j,1<<X) printf("%lld ",mul[node].data[i][j]); puts(""); } puts("");
}

void update(int node, int left, int right, int n){
  int i, j;
  int n1 = node * 2 + 1, n2 = node * 2 + 2, sz = right - left;

  if(n < left) return;
  if(n >= right) return;

  if(sz==1){
    rep(i,1<<X) rep(j,1<<X) mul[node].data[i][j] = val[left].data[i][j];
    return;
  }

  update(n1, left, left+sz/2, n);
  update(n2, left+sz/2, right, n);
  llMatrixMultipleMod(&mul[n2], &mul[n1], &mul[node], MD);
}


int main(){
  int i, j, k, q, fg;
  ll now, nowx, nowy;
  ll res;
  llMatrix mt[4];
  llMatrix cur = newLLMatrix(5,5);
  llMatrix tmp = newLLMatrix(5,5);
  llMatrix pw = newLLMatrix(5,5);
  map<ll,int> mp, ind;
  map<ll,int>::iterator it;
  set<ll> s;
  set<ll>::iterator sit;

  rep(i,41000)  val[i] = newLLMatrix(5,5);
  rep(i,200000) mul[i] = newLLMatrix(5,5);

  mem = malloc(30000000);
  rep(i,4) mt[i] = newLLMatrix(5,5);

  reader(&X);
  reader(&Y);
  reader(&N);
  rep(i,N) reader(x+i), reader(y+i), x[i]--, y[i]--;

  rep(i,41000) val[i].r=val[i].c=(1<<X);
  rep(i,200000) mul[i].r=mul[i].c=(1<<X);

  rep(i,1<<X) mt[i].r = mt[i].c = (1<<X);
  rep(i,1<<X) rep(j,1<<X){
    rep(k,1<<X) mt[i].data[j][k] = 0;
    if(i&j) continue;
    
    mt[i].data[j][0] += 1;

    if(X==1){
      if(i==0 && j==0) mt[i].data[j][1] += 1;
      continue;
    }
    
    if(i==0 && j==0) mt[i].data[j][0] += 1;
    if(i==0 && j==0) mt[i].data[j][3] += 1;

    if((!(i&1)) && (!(j&1))) mt[i].data[j][1] += 1;
    if((!(i&2)) && (!(j&2))) mt[i].data[j][2] += 1;
  }


  rep(i,N) s.insert(y[i]);
  s.insert(Y);
  num = s.size() * 2;
  k = 0;
  nowy = 0;
  for(sit = s.begin(); sit != s.end(); sit++){
    llMatrixPowerMod(&mt[0], &val[k], (*sit)-nowy, MD, mem);
    nowy = (*sit);
    k++;

    rep(i,1<<X) rep(j,1<<X) val[k].data[i][j] = mt[0].data[i][j];
    ind[*sit] = k;
    nowy++;
    k++;
  }

  rep(i,1<<X) rep(j,1<<X) val[num-1].data[i][j] = mt[(1<<X)-1].data[i][j];

  init(0, 0, num);

  mp.clear();
  mp[Y] = 3;
  rep(q,N){
    mp[y[q]] ^= (1<<x[q]);

    k = ind[y[q]]; fg = mp[y[q]];
    rep(i,1<<X) rep(j,1<<X) val[k].data[i][j] = mt[fg].data[i][j];

    update(0, 0, num, k);
    
    res = mul[0].data[0][0];
    writer((int)res, '\n');
  }

  return 0;
}

Current time: 2017年09月26日02時00分36秒
Last modified: 2014年08月06日02時05分47秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Regular_Contest ARC025 ARC_D
トップページに戻る

Logged in as: unknown user (not login)

ログイン: