Codeforces #148 div1A,div2C Not Wool Sequences

これからボチボチCodeforcesの和訳＆解説＆コードとかを公開していくかもしれません
基本的に、自分が受けたコンテストを1日後ぐらいに公開する予定です

URL: http://www.codeforces.com/contest/238/problem/A

問題概要

ある数列について、隣接した空でない部分列のxorを取ったものが0となる部分列があるとき、その数列はWool sequenceとする
長さNで要素が0から(2^m)-1でWool Sequenceでない数列の数を10^9+9で割ったあまりを求めよ。
1<=N,m<=10^5

方針

i番目まで決まったとすると、
[0,i)までの数列の部分列にxorして0となるものはない。
i番目をx(x!=0)という数にして、[j,i](0<=j

using namespace std;
static const int INF =500000000;
typedef pair<int,int> pi;
const long long mod=1000000009;
long long mpow(long long a,int k){
	long long res=1;
	while(k){
		if(k&1){
			res=res*a%mod;
		}
		a=a*a%mod;
		k>>=1;
	}
	return res;
}

int main(){
	int n,m;
	cin>>n>>m;
	long long res=1;
	for(int i=0;i<n;++i){
		res*=mpow(2,m)-1-i;
		res%=mod;
	}
	cout<<res<<endl;

	return 0;
}