Submission #4034146

---

Source Code Expand

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

#define MOD 1000000007ll
#define MAXN 200005
typedef long long ll;
typedef unsigned long long ull;
#define min(a, b) (((a) < (b)) ? (a) : (b))
#define max(a, b) (((a) > (b)) ? (a) : (b))

ll read()
{
    char c = getchar();
    ll ret = 0;
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') ret = ret * 10 + c - '0', c = getchar();
    return ret;
}

int N;
ll blocklen, pn = 1, pk = 0, anst = 1, inv[MAXN], mul[MAXN], mulinv[MAXN], ans[MAXN], inv2 = (MOD + 1) >> 1; //pn, pk是莫队用的指针，anst是临时答案，mul是阶乘，mulinv是阶乘逆元，inv是逆元，ans存答案（因为离线存储打乱了顺序），inv2是2的逆元
struct query
{
    ll n, k, id, block;
} Q[MAXN];
bool cmp(query q1, query q2)
{
    if (q1.block != q2.block) return q1.block < q2.block;
    else return q1.k < q2.k;
}
ll ask(ll n, ll m)
{
    return ((mul[n] * mulinv[m]) % MOD * mulinv[n - m]) % MOD;
} 
void move(int t)
{
    switch(t)
    {
        case 1: anst = ((anst + ask(pn, pk + 1)) % MOD + MOD) % MOD, ++pk; break;
        case 2: anst = ((anst - ask(pn, pk)) % MOD + MOD) % MOD, --pk; break;
        case 3: anst = (((2 * anst) % MOD - ask(pn, pk)) % MOD + MOD) % MOD, ++pn; break;
        case 4: anst = ((inv2 * ((anst + ask(pn - 1, pk)) % MOD)) % MOD + MOD) % MOD, --pn; break;
    }
}

int main()
{
    N = read(), blocklen = sqrt(N);
    int i;
    inv[1] = 1, mul[0] = mulinv[0] = 1;
    for (i = 2; i <= 100000; ++i) inv[i] = ((MOD - MOD / i) * inv[MOD % i]) % MOD, mul[i] = (mul[i - 1] * (ll)i) % MOD; //线性求逆元
    for (i = 1; i <= 100000; ++i) mul[i] = (mul[i - 1] * i) % MOD, mulinv[i] = (mulinv[i - 1] * inv[i]) % MOD;
    for (i = 1; i <= N; ++i) Q[i].n = read(), Q[i].k = read(), Q[i].id = i, Q[i].block = Q[i].n / blocklen;
    sort(Q + 1, Q + N + 1, cmp);
    for (i = 1; i <= N; ++i)
    {
        while (pn < Q[i].n) move(3);
        while (pn > Q[i].n) move(4);
        while (pk < Q[i].k) move(1);
        while (pk > Q[i].k) move(2); 
        ans[Q[i].id] = anst;
    }
    for (i = 1; i <= N; ++i) printf("%lld\n", ans[i]);
}

Submission Info

Judge Result