題意
有n只螞蟻分別在1到n的位置（左右還有位置0和位置n + 1）里烦，他們的重量分別是1到n废菱，其實n只螞蟻分別隨機選取左右中的一個方向同時開始行走（走到頭就轉(zhuǎn)向），兩只螞蟻相遇就打架，較重的獲勝，較輕的被吃掉崭参，并且重量變成兩者之和，問最后第k只螞蟻活下來的方案數(shù)（總共2 ^ n種情況）
樣例
3
2 1 Case #1: 0
3 2 Case #2: 4
4 2 Case #3: 4
樣例2中的方案：左左左款咖，左左右何暮，右左左奄喂，右左右
2 ≤ N ≤ 10 ^ 6
1 ≤ K ≤ N
思路
（1）第k只螞蟻必然是先向左（k != n的情況下），吃掉左邊所有的螞蟻海洼，然后向右跨新。我們先計算出吃掉k左邊所有螞蟻的方案數(shù)，可以分為兩步坏逢，首先是直接吃掉一段靠近k的且向右走的螞蟻域帐，然后靠左的一段形成一致大螞蟻，然后被靠右的吃掉是整。比如k = 6俯树，5向右走，6吃掉5贰盗；4向左走，將1阳欲， 2舵盈， 3， 4形成一只重量是10的大螞蟻球化，然后被6和5形成的11大螞蟻吃掉秽晚。我們可以枚舉靠右的那一段。
（2）在1到k都被吃掉后筒愚，可以動規(guī)解決后面的情況赴蝇。dp[i]表示前i只螞蟻已經(jīng)合并的方案數(shù)，可以枚舉這只大螞蟻最后吃掉的那一段巢掺，那么：
dp[i] = sigma{dp[j] | j < i && 1到j形成的大螞蟻可以吃掉j + 1到i形成的大螞蟻}
代碼
#define rep(i, n) for (int i = 0; i < (n); i++)
#define FOR(i, n, m) for (int i = (n); i <= (m); i++)
const int N = 1000000, MOD = 1000000007;
int T, n, m;
LL pre[N + 5], c[N + 5];
LL dp[N + 5], sd[N + 5];
void init() {
pre[0] = 0, c[0] = 1;
FOR (i, 1, N) {
pre[i] = pre[i - 1] + i;
c[i] = c[i - 1] * 2 % MOD;
}
}
int solve() {
if (n == 1) return 2;
if (m == 1) return 0;
LL sum = 0, tmp = 1, p = m, now = pre[p];
FORD (i, m, 2) {
sum += i;
if (sum <= pre[m] - sum) continue;
tmp = (tmp + c[i - 2]) % MOD;
}
if (m == n) return tmp * 2 % MOD;
memset(dp, 0, sizeof(dp));
memset(sd, 0, sizeof(sd));
dp[m] = tmp, sd[m] = tmp;
FOR (i, m + 1, n) {
while (now < pre[i] - now) now += (++p);
dp[i] = (sd[i - 1] - sd[p - 1]) * (i == n ? 2 : 1);
dp[i] = (dp[i] + 2 * MOD) % MOD;
sd[i] = (sd[i - 1] + dp[i]) % MOD;
//sc3(i, p, dp[i]);
}
return (int) dp[n];
}
int main() {
file_r("in.txt");
file_w("out.txt");
int cas = 0;
scanf("%d", &T);
//T = 55;
init();
//file_w("out.txt");
while (T--) {
scanf("%d %d", &n, &m);
//FOR (i, 1, 10) FOR (j, 1, i) {
// n = i, m = j;
printf("Case #%d: %d\n", ++cas, solve());
//}
}
return 0;
}
