# 【UVALive 7505】Hungry Game of Ants（DP）

2016-10-29

，其次，它会把左边所有蚂蚁吃掉然后掉头。

&sum;j > &sum;1&le;c&le;jant[c]

&sum;1&le;c=&sum;j&le;c&le;iant[c]，即j到i合并，k吃掉左边的再吃到j-1。

```#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define Pr pair
#define fwrite(ch) freopen(ch,"w",stdout)

using namespace std;
const int INF = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-8;
const int maxn = 1123456;

LL dp[maxn];

LL Pow(LL a,LL b)
{
LL ans = 1;

while(b)
{
if(b&1) ans = ans*a%mod;
b >>= 1;
a = a*a%mod;
}

return ans;
}

LL Sum(LL x)
{
return x*(x+1)/2;
}

LL Search(LL l,LL r,LL k)
{
if(r < l) return 1;
LL sum = Sum(r);
LL ans = -1;

while(l <= r)
{
LL mid = (l+r)>>1;

if(sum-Sum(mid)+k > Sum(mid))
{
ans = mid;
l = mid+1;
}
else r = mid-1;
}

if(ans == -1) return 0;

return Pow(2,ans);
}

LL solve(int n,int k)
{
LL ans = 0;

dp[k] = Search(1,k-1,k);
int l = k;
ans = dp[k];

for(int i = k+1; i <= n; ++i)
{
while(l < i && Sum(l) < Sum(i)-Sum(l)) ans = ((ans-dp[l++])%mod+mod)%mod;

dp[i] = ans;
ans = (ans+dp[i])%mod;

}

return dp[n]*2%mod;
}

int main()
{
//fwrite("");

int t,n,k;

scanf("%d",&t);

for(int z = 1; z <= t; ++z)
{
scanf("%d%d",&n,&k);
printf("Case #%d: %lld\n",z,solve(n,k));
}

return 0;
}```