HDU 6333 Problem B. Harvest of Apples——莫队

HDU 6333 Problem B. Harvest of Apples——莫队

题意：

There are nn apples on a tree, numbered from 11 to nn.  Count the number of ways to pick at most mm apples.

思路：

sum(n, m) = 2sum(n-1, m) - c(n-1, m)

sum(n,m) = sum(n, m-1) + c(n, m)

可以发现若知道了sum(n, m)可以在O（1）时间内推出sum(n-1,m),sum(n,m-1),sum(n+1, m),sum(n,m+1)

可以用莫队

#include #include #include #include #include using namespace std;typedef long long ll;const int maxn = 1e5 + 10;const int mod = 1e9 + 7;const int block = 316;int belong[maxn];ll fac[maxn], inv[maxn];struct Modui { int l, r, id; ll ans;}modui[maxn];bool cmp1(Modui &x, Modui &y) { if (belong[x.l] != belong[y.l]) return x.l < y.l; return x.r < y.r;}bool cmp2(Modui &x, Modui &y) { return x.id < y.id;}ll mpow(ll x, int y) { ll ans = 1; while (y) { if (y & 1) ans = ans * x % mod; x = x * x % mod; y >>= 1; } return ans;}ll C(int x, int y) { if (x < y) return 0; return fac[x] * inv[y] % mod * inv[x-y] % mod;}void init() { fac[0] = 1; for (int i = 1; i < maxn; i++) fac[i] = fac[i-1] * i % mod; inv[maxn-1] = mpow(fac[maxn-1], mod - 2); for (int i = maxn - 2; ~i; --i) inv[i] = inv[i + 1] * (i + 1) % mod; for (int i = 0; i < maxn; i++) belong[i] = i / block;}int main() { init(); int T; scanf("%d", &T); for (int i = 1; i <= T; i++) { scanf("%d%d", &modui[i].l, &modui[i].r); modui[i].id = i; } sort(modui+1, modui+1+T, cmp1); int l = 1, r = 0; ll sum = 1; for (int i = 1; i <= T; i++) { while (l < modui[i].l) sum = ((sum*2%mod-C(l++, r))%mod+mod)%mod; while (l > modui[i].l) sum = (sum+C(--l, r))%mod*inv[2]%mod; while (r < modui[i].r) sum = (sum+C(l, ++r))%mod; while (r > modui[i].r) sum = ((sum-C(l, r--))%mod+mod)%mod; modui[i].ans = sum; } sort(modui+1, modui+1+T, cmp2); for (int i = 1; i <= T; i++) { printf("%lld\n", modui[i].ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。