【链接】 我是链接,点我呀:)
【题意】
【题解】
假设T[i][j]表示的是杨辉三角第i层前j项的和。 会发现它同样满足杨辉三角的性质。 即 T[i][j] = T[i-1][j-1]+T[i-1][j] ····① 同时还有T[i][j] = T[i][j-1]+C[i][j] ····② 根据②式我们可以推出来①式的另外一种形式 T[i][j] = 2*T[i-1][j]-C[i-1][j] ···③ 至此我们可以根据②③两式 用T[i][j]得到T[i-1][j],T[i+1][j],T[i][j-1],T[i][j+1]也即得到和它相邻的4个T的值。 考虑到给了我们n个询问。 我们可以考虑用莫队算法来搞。 做莫队之前先将询问分块。 m值为[1..sqrt(maxn)]的放在第1个vector中 m值为[sqrt(maxn)+1,sqrrt(maxn)*2]的放在第2个vector中 以此类推。 然后我们把这个maxn/sqrt(maxn)个块逐块处理。 每个块按照n值升序排。 这样我们在做莫队的时候。n值只会递增。 m值在sqrt(maxn)内波动。可以用上面得到的结论O(1)变化。 O(能过)【代码】
#include <bits/stdc++.h>
#define ll long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define all(x) x.begin(),x.end()
#define pb push_back
#define lson l,mid,rt<<1
#define rei(x) scanf("%d",&x)
#define rel(x) scanf("%lld",&x)
#define res(x) scanf("%s",x)
#define rson mid+1,r,rt<<1|1
using namespace std;
const double pi = acos(-1);
const int dx[4] = {0,0,1,-1};
const int dy[4] = {1,-1,0,0};
const int N = 1e5+10;
const ll MOD = 1e9+7;
struct abc{
int n,m,id;
}a[N+10];
namespace COMB {
int F[N], Finv[N], inv[N]; //F是阶乘，Finv是逆元的阶乘
void init(){
inv[1] = 1;
for(int i = 2; i < N; i ++){
inv[i] = (MOD - MOD / i) * 1LL * inv[MOD % i] % MOD;
}
F[0] = Finv[0] = 1;
for(int i = 1; i < N; i ++){
F[i] = F[i-1] * 1LL * i % MOD;
Finv[i] = Finv[i-1] * 1LL * inv[i] % MOD;
}
}
ll comb(int n, int m){ //comb(n, m)就是C(n, m)
if(m < 0 || m > n) return 0;
return F[n] * 1LL * Finv[n - m] % MOD * Finv[m] % MOD;
}
}
bool cmp(abc a,abc b){
return a.n < b.n;
}
ll ans[N+10];
int in[N+10];
vector<abc> kuai[N+10];
int main(){
#ifdef LOCAL_DEFINE
freopen("rush_in.txt", "r", stdin);
#endif
ios::sync_with_stdio(0),cin.tie(0);
COMB::init();
int T;
cin >> T;
for (int i = 1;i <= T;i++) {
cin >> a[i].n >> a[i].m;
a[i].id = i;
}
int kuai_len = sqrt(100000);
int cnt = 1;
for (int scnt = 1;scnt<=100000;scnt+=kuai_len,++cnt){
for (int j = scnt;j < scnt+kuai_len && j <=100000;j++){
in[j] = cnt;
}
}
cnt--;
for (int i = 1;i <= T;i++){
int kuai_index = in[a[i].m];
kuai[kuai_index].push_back(a[i]);
}
for (int i = 1;i <= cnt;i++)
if ((int)kuai[i].size()>0){
sort(kuai[i].begin(),kuai[i].end(),cmp);
int nn = a[0].n,mm = -1;
ll cur = 0;
/*
T[n+1][m] = 2*cur-c[n][m];
T[n][m+1] = cur+c[n][m+1];
T[n][m-1] = cur-c[n][m];
*/
for (int j = 0;j < (int)kuai[i].size();j++){
while (nn<kuai[i][j].n){
cur = (2*cur%MOD-COMB::comb(nn,mm)+MOD)%MOD;
nn++;
}
while (mm<kuai[i][j].m){
cur = (cur + COMB::comb(nn,mm+1))%MOD;
mm++;
}
while (mm>kuai[i][j].m){
cur = (cur - COMB::comb(nn,mm)+MOD)%MOD;
mm--;
}
ans[kuai[i][j].id] = cur;
}
}
for (int i = 1;i <= T;i++){
cout<<ans[i]<<endl;
}
return 0;
}