AtCoder Beginner Contest #009 D問題 - 漸化式

Source

AtCoder Beginner Contest #009
問題文

問題概要

数列 $\{A_k\}_{k=1}^\infty$ を以下のように定める:
$A_1,A_2,\ldots,A_K$ は与えられる.
$A_{N+K} = (C_1\ {\rm AND}\ A_{N+K-1})\ {\rm XOR}\ (C_2\ {\rm AND}\ A_{N+K-2})\ {\rm XOR}\ \cdots \ {\rm XOR}\ (C_K\ {\rm AND}\ A_N), \;\; N \geq 1$
$A_M$ を求める問題.

解法

ベクトルと行列を用いて $2$ 項間の線形差分方程式にして考える.
足し算を ${\rm XOR}$ に,掛け算を ${\rm AND}$ に読み変えて($({\mathbb Z}/2{\mathbb Z})^{32}$ で考える),行列べき乗して一般項を求めれば良い.

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)

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


int K, M;
unsigned all;

struct MMM{
  unsigned d[101][101];
};

MMM mul(MMM a, MMM b){
  int i, j, k;
  MMM c;
  rep(i,K) rep(j,K) c.d[i][j] = 0;
  rep(i,K) rep(j,K) rep(k,K) c.d[i][j] ^= (a.d[i][k]&b.d[k][j]);
  return c;
}

MMM pw(MMM a, int M){
  int i, j;
  MMM res;
  if(M==0){
    rep(i,K) rep(j,K) res.d[i][j] = 0;
    rep(i,K) res.d[i][i] = all;
    return res;
  }
  res = pw(a, M/2);
  res = mul(res, res);
  if(M%2) res = mul(res, a);
  return res;
}

int main(){
  int i, j;
  unsigned A[120], C[120], res;
  MMM mat;

  reader(&K,&M);
  rep(i,K) reader(A+i);
  rep(i,K) reader(C+i);

  if(M <= K){
    writer(A[M-1], '\n');
    return 0;
  }

  rep(i,40) all |= (1U<<i);

  rep(i,K) rep(j,K) mat.d[i][j] = 0;
  rep(i,K-1) mat.d[i][i+1] = all;
  rep(i,K) mat.d[K-1][i] = C[K-1-i];


  mat = pw(mat, M-K);
  res = 0;
  rep(i,K) res ^= (A[i]&mat.d[K-1][i]);
  writer(res, '\n');

  return 0;
}

Current time: 2017年09月26日01時56分01秒
Last modified: 2014年05月25日00時00分50秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Beginner_Contest ABC009 ABC_D
トップページに戻る

Logged in as: unknown user (not login)

ログイン: