codeforces 238A

タイトル:http://codeforces.com/problemset/problem/238/A
簡単なデータの問題を表して、思考の依然として不十分です.実は正しい考えは 2^m個の数の中からn個の数を選択する異種または1つのシーケンスがある以上、任意のサブシーケンスの異種または和は0ではない.
そう考えることができます
n=1の場合、ans=2^m;  n=2の場合、つまり2番目に1番目と同じ数を選択できないのでans= 2^m*(2^m-1);  
n=3の場合、3番目のビットの数は、2番目のビットの数と同じ数を選択することも、1番目のビットと2番目のビットの異或の後に得られる数と同じ数を選択することもできず、この2つの数は必然的に異なる.もしこの2つの数が同じなら、明らかに前はもう題意に合わない.だからans=2^m*(2^m-1)*(2^m-2);
同じ理屈.n=X(n=3と同じ思考)

#include<cstdio>
using namespace std;
const int mod = 1000000000+9;

int main(){
    int n,m;  int mul=1;
    scanf("%d%d",&n,&m);
    while(m--)   mul=(mul*2)%mod;
    long long ans=1;
    for(int i=1;i<=n;i++)  ans=  (ans*(mul-i) )%mod;
    printf("%I64d
",ans);
    return 0;

}