SRM448 div2 medium

nが奇数のとき、

1 2 3 4 5
2 4 1 3 5  (1+1)%5
4 3 2 1 5  (2+2)%5
3 1 4 2 5  (4+4)%5
1 2 3 4 5  (3+8)%5
<--5は動かない

nが偶数のとき

1 2 3 4
2 4 1 3
4 3 2 1
3 1 4 2
1 2 3 4  <--5のときとまったく同じ。
...

奇数と偶数で状況が変わることが分かる。2のべき乗とかは関係しない。
一応、m <= 1000000なので、2^mをやるわけにはいかない。なので、MODをもちいて計算する。
n = 9のとき
m
1 2 3 4  5  6
1 2 4 8 16 32  MOD 9

1 2 4 8  7  5
2 4 8 7  5  1 ..

class TheCardShufflingDivTwo {
public:
  int shuffle(int n, int m) {
		n = (int)n/2 * 2 + 1;
		int cur = 1;
		for(int i = 1; i <= m; i++) {
			cur = (cur*2)%n;
		}
		return cur-1 + 1;
	}

};