题意：n 只蚂蚁在横轴（长度 n+1）上，第 i 只蚂蚁在坐标 i 上，重量为 i，蚂蚁可以选择向左走或向右走，当两只蚂蚁相遇时大蚂蚁吃掉小蚂蚁，重量增加小蚂蚁的重量，如果重量相同，左边的蚂蚁吃掉右边的蚂蚁。给出 n 和 k，问第 K 只蚂蚁最后留下的情况数。 i 从第 k 只蚂蚁开始考虑：
i = k 时，也就是说这是我们当作数轴上只有 k 个蚂蚁，求最后一只存活的情况数。首先我们应该清除：假设 k 是所有蚂蚁中向左走的最右边那一只，那么 1~k 所有蚂蚁都会变成一个整体，重量为 j*（1+j）/2。 所以我们从 k 往前找到 j，使 j，j+1，j+2,……，k 的和大于 a1[i]（前缀和）的一半，也就是说 j~k 蚂蚁的重量和大于 1~j-1 蚂蚁的重量和，此时 j~k-1 所有蚂蚁方向都是固定的，向右，蚂蚁 k 的方向可以向左也可以向右，因为他是最后一只蚂蚁。可以用后缀和减去前缀和计算，此时 dp[i] = 2^（j+1）.
i > k 时，考虑状态转移方程：dp[n] += dp[n-1]/2*2 ，也就是 dp[n] += dp[n-1]，/2 是因为 n 的出现使 n-1 只能向右走，*2 是因为 n 两个方向都可以走。这样我们设数组 m[j] 表示 j 的后缀和（包括 j）大于前缀和（不包括 j）的最小坐标，a2[w]表示 dp 的前缀和。所以 i > k 时，dp[n] = dp[n-1]+dp[n-2]+ ……+dp[w] = a2[n-1]-a2[w-1]，其中 w = m[i]，由于是从左开始遍历的，整个过程 O（n）时间内就可以完成。
#include<cstring>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
const int mod = 1e9+7;
long long dp[1000005]; //dp[i]表示考虑到第i个蚂蚁
long long poww[1000005]; //2^n
long long a1[1000005]; //蚂蚁重量前缀和
long long a2[1000005]; //dp[]的前缀和
long long m[1000005];
void init(){
poww[0] = 1;
a1[0] = 0;
for(int i = 1; i < 1000005; i++){
poww[i] = (poww[i-1]<<1)%mod;
poww[i] %= mod;
}
for(int i = 1; i < 1000005; i++){
a1[i] = a1[i-1]+i;
}
m[0] = 0;
for(long long i = 1; i < 1000005; i++){
long long tmp = m[i-1];
long long tmp2 = i*(i+1);
while(2*tmp*(tmp+1) < tmp2) tmp++;
m[i] = tmp;
}
}
int main(){
//freopen("a.txt", "r", stdin);
int t;
scanf("%d", &t);
init();
for(int cas = 1; cas <= t; cas++){
memset(a2, 0, sizeof(a2));
int n, k;
scanf("%d%d", &n, &k);
printf("Case #%d: ", cas);
if(n == 1 && k == 1){
cout << "2" << endl;
continue;
}
memset(dp, 0, sizeof(dp));
for(long long i = k; i <= n; i++){
if(i == k){
long long sum = k;
for(int j = k-1; j >= 1; j--){
if(sum > a1[j]){
dp[k] = poww[j+1];
break;
}
sum += j;
}
a2[i] = dp[i];
}else{
if(m[i] >= k)
dp[i] = ((a2[i-1]-a2[m[i]-1])%mod+mod)%mod;
else
dp[i] = a2[i-1];
a2[i] = (a2[i-1]+dp[i])%mod;
}
}
printf("%lldn", dp[n]);
}
return 0;
}