yukicoder : No.492 IOI数列

3問目で軽いミスと、4問目で問題文読み落としによるタイムロスが痛かった。
http://yukicoder.me/problems/no/492

問題

以下の数列A[n]を考える。

• A[1]=1
• A[n]=A[n-1]*100 + 1 (n＞1)

Nが与えられるので、A[N]%1000000007とA[N]%101010101010101010101を求めよ。

解法

まず前者を考える。
より、２次元行列の(N-1)乗を求めればA[1]からA[N]が求められる。

後者も多倍長演算が使える言語なら同じ解法で解ける。
M=101010101010101010101とする。
そうでない場合を考える。A[N]が仮に21桁以上ある場合、その上位21桁はMに10を何度か掛けると一致するはずである。
よってその場合、A[N] mod Mを考えると上位21桁(とそれによって生じるleading zeroを合わせると22桁)を無視できる。
これはA[N]をA[N-11]にするのと同義である。
この処理を繰り返し、A[N%11]を答えればよい(A[0]=0とする)

ll N;

const int MAT=2;
ll G[MAT][MAT],G2[MAT][MAT];
ll mo;
void powmat(ll p,int n,ll a[MAT][MAT],ll r[MAT][MAT]) {
	int i,x,y,z;
	ll a2[MAT][MAT];
	FOR(x,n) FOR(y,n) a2[x][y]=a[x][y];
	FOR(x,n) FOR(y,n) r[x][y]=(x==y);
	while(p) {
		ll h[MAT][MAT];
		if(p%2) {
			FOR(x,n) FOR(y,n) h[x][y]=0;
			FOR(x,n) FOR(z,n) FOR(y,n) h[x][y] += (r[x][z]*a2[z][y]) % mo;
			FOR(x,n) FOR(y,n) r[x][y]=h[x][y]%mo;
		}
		FOR(x,n) FOR(y,n) h[x][y]=0;
		FOR(x,n) FOR(z,n) FOR(y,n) h[x][y] += (a2[x][z]*a2[z][y]) % mo;
		FOR(x,n) FOR(y,n) a2[x][y]=h[x][y]%mo;
		p>>=1;
	}
}

void solve() {
	int i,j,k,l,x,y; string s;
	cin>>N;
	
	G[0][0]=100;
	G[0][1]=1;
	G[1][1]=1;
	mo=1000000007;
	
	powmat(N-1,2,G,G2);
	cout<<(G2[0][0]+G2[0][1])%mo<<endl;
	
	N=N%11;
	if(N==0) _P("0\n");
	else {
		FOR(i,N-1) _P("10");
		_P("1\n");
	}
}

まとめ

後者はだいぶオマケっぽいね。