HDU6333 Harvest of Apples (杭电多校4B)

时间:2021-08-01 00:20:30

这莫队太强啦

先推公式S(n,m)表示从C(n, 0) 到 C(n, m)的总和

1.S(n, m)   = S(n, m-1) + C(n, m) 这个直接可以转移得到

2.S(n, m)   = S(n, m+1) - C(n, m+1) 通过变形就可以得到。

3.S(n, m)   = C(n, 0) + C(n, 1) + C(n, 2) + ... + C(n, m)

     = C(n-1, 0) + C(n-1, 0) + C(n-1, 1) + C(n-1, 1) + C(n-1, 2) + ... +C(n-1, m-1) + C(n-1, m)

     = 2S(n-1, m) - C(n-1, m)

4.S(n, m)   = (S(n+1, m) + C(n, m) ) / 2

然后求C(n, m)的时候打表存不下,所以就用C(n, m) = n!/ (m! * (n-m)!)

然后除法部分用逆元保证一下精度就可以了

然后就可以直接套莫队了

#include<map>
#include<set>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lowbit(x) (x & (-x)) typedef unsigned long long int ull;
typedef long long int ll;
const double pi = 4.0*atan(1.0);
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+;
const int maxm = ;
const int mod = 1e9+;
using namespace std; int n, m, tol, T;
int block;
struct Node {
int l;
int r;
int id;
bool operator < (Node a) const {
return l/block != a.l/block ? l/block < a.l/block : r < a.r;
}
};
Node node[maxn];
ll res[maxn];
ll fac[maxn];
ll inv[maxn];
ll ans; void init() {
ans = ;
memset(res, , sizeof res);
memset(node, , sizeof node);
} ll fa_pow(ll a, ll b) {
ll ans = ;
a %= mod;
while(b) {
if(b & )
ans = ans * a % mod;
a = a * a % mod;
b >>= ;
}
return ans % mod;
} void handle() {
fac[] = ;
inv[] = ;
for(int i=; i<=; i++) {
fac[i] = fac[i-] * i;
fac[i] %= mod;
inv[i] = fa_pow(fac[i], mod-);
}
} ll C(int n1, int m1) {
if(m1 > n1) return ;
ll ans = fac[n1] * inv[m1] % mod * inv[n1-m1] % mod;
return ans;
} int main() {
init();
handle();
scanf("%d", &n);
block = sqrt(n);
for(int i=; i<=n; i++) scanf("%d%d", &node[i].l, &node[i].r), node[i].id = i;
sort(node+, node++n);
int L = ;
int R = ;
for(int i=; i<=n; i++) {
while(L > node[i].l) {
L--;
ans = (ans + C(L, R)) % mod * inv[] % mod;
}
while(L < node[i].l) {
ans = (ans * % mod - C(L, R)) % mod + mod;
ans %= mod;
L++;
}
while(R < node[i].r) {
R++;
ans = (ans + C(L, R)) % mod;
}
while(R > node[i].r) {
ans = (ans - C(L, R) % mod) + mod;
ans %= mod;
R--;
}
res[node[i].id] = ans;
}
for(int i=; i<=n; i++) printf("%I64d\n", res[i]);
return ;
}