题目链接 题意:一个长为n+1的杆子。上面有n个蚂蚁，第i个蚂蚁在距离左边第i个位置，重量为i。开始后，所有蚂蚁随机从向左或者向右以相同的速度开始移动，如果走到杆子的头，他会立刻掉头。如果两个蚂蚁相遇了，则重量大的那个蚂蚁会把小的吃了，他的体重会增加小的体重。并继续往前走，如果两个蚂蚁重量相同，则左边会吃掉右边。问：第k个蚂蚁有多少种幸存到最后的情况。 题解： 首先，如果第k个蚂蚁开始往右走必死无疑。只能向左走，不难想到此时k蚂蚁只有把先k-1只蚂蚁全部吃掉之后才会和他右边的蚂蚁相遇。也就是说，在和开始右边的蚂蚁相遇时，他的体重一定是 ∑ 1 k i \sum_1^ki ∑1ki。这里不妨把k蚂蚁的移动分为两个阶段，吃左面蚂蚁和吃右面蚂蚁。
第一阶段（吃左面蚂蚁）： 枚举k蚂蚁左面第一个往左走的蚂蚁c，显然如果 ∑ c + 1 k i > ∑ 1 c i \sum_{c+1}^ki>\sum_1^ci ∑c+1ki>∑1ci则是一种合法情况，这时对于蚂蚁1到蚂蚁c-1，他们可以任意选择方向。最后累计所有情况。当然最后结果要+1，因为还有一个1到k-1都往右走的情况。
第二阶段（吃右面蚂蚁）： 我们把第一阶段的答案赋值给dp[k]进行dp。 我们对于dp[p]，代表考虑到第p个蚂蚁，最后一个蚂蚁往左走的方案数，同样枚举在他之前第一个往左走的蚂蚁c。显然蚂蚁k在与p相遇前会吃掉前c个蚂蚁。所以体重为 ∑ 1 c i \sum_1^ci ∑1ci如果满足条件 ∑ 1 c i > = ∑ c + 1 p i \sum_1^ci>=\sum_{c+1}^pi ∑1ci>=∑c+1pi则为合法状态，dp[i]需要累加dp[c]。显然，这个判定关系是单调的，遂可以二分或者尺取。样例1e7，二分会tle，所以用尺取。最后答案要*2，因为最后一只蚂蚁可以往右走。
下面是ac代码：
#include <iostream> #include <string> #include <cstring> #include <vector> #include <cstring> #include <cstdio> #include <algorithm> #include <map> #include <cmath> #define ll long long using namespace std; const int N = 2e6+5; const int inf= 0x3f3f3f3f; const int mod = 1e9+7; inline ll getn(int l, int r) { if (l > r) return 0; return 1ll * (r - l + 1) * (r + l) / 2; } ll dp[N]; ll in[N]; int main() { int t; cin >> t; int t0 = 1; in[0] = 1; for (int i = 1; i <= N-2; i++) in[i] = in[i-1] * 2 % mod; while(t--) { int n, k; scanf("%d%d", &n, &k); ll ans = 0; for (int i = 0; i <= n; i++) dp[i] = 0; for (int i = 1; i < k; i++) { ll r = getn(i+1, k); ll l = getn(1, i); if (l >= r) continue; ans = (ans + in[i-1] % mod) % mod; } ans++, ans %= mod; ll mx = getn(1, k); ll ansr = 1; int c = k; dp[k] = ans; for (int i = k+1; i <= n; i++) { while(c < i && getn(1, c) < getn(c+1, i)) ans = ((ans - dp[c++]) % mod + mod) % mod; dp[i] = ans; ans = (ans + dp[i]) % mod; } printf("Case #%d: %lld\n",t0++, dp[n]*2 % mod); } return 0; }