B. Harvest of Apples

题意

There are n apples on a tree, numbered from 1 to n.

Count the number of ways to pick at most m apples.

$1 \leq T \leq 1e5, 1 \leq n,m \leq 1e5$

分析

设$S(n,m) = \sum_{i=1}^{m}C(n,i)$

然后有转移$S(n,m) = 2S(n-1,m) - C(n-1,m) = S(n,m-1) + C(n,m)$

然后就莫队瞎搞搞...

注意分块排序时候的m要从小到大,不然会有n < m的情况出现。

代码

// ybmj
#include <bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define lson_len (len - (len >> 1))
#define rson_len (len >> 1)
#define pb(x) push_back(x)
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define first fi
#define second se
#define my_unique(a) a.resize(distance(a.begin(), unique(a.begin(), a.end())))
#define my_sort_unique(c) (sort(c.begin(), c.end())), my_unique(c)
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
int S;
struct Node {
    int n, m, id;
    ll ans;
};
bool cmp(const Node& A, const Node& B) {
    if (A.n / S == B.n / S) return A.m < B.m;   // 注意大小
    return A.n / S < B.n / S;
}
Node a[maxn];

ll f[maxn], inv[maxn];

ll Pow(ll a, ll b) {
    ll ret = 1;
    while (b) {
        if (b & 1) ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}
void CalFact() {
    f[0] = 1;
    for (int i = 1; i < maxn; i++) f[i] = (f[i - 1] * i) % mod;
    inv[maxn - 1] = Pow(f[maxn - 1], mod - 2);
    for (int i = maxn - 2; ~i; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
}
inline ll C(int n, int m) { return f[n] * inv[m] % mod * inv[n - m] % mod; }
int main() {
// /*
#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
#endif
    // */
    std::ios::sync_with_stdio(false);
    CalFact();
    int n;
    scanf("%d", &n);
    S = sqrt(n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i].n, &a[i].m);
        a[i].id = i;
    }
    sort(a + 1, a + n + 1, cmp);
    int nn = 1, mm = 0;
    ll ans = 1;
    for (int i = 1; i <= n; i++) {
        while (nn < a[i].n) {
            ans = (2 * ans % mod - C(nn, mm) + mod) % mod;
            nn++;
        }
        while (nn > a[i].n) {
            nn--;
            ans = (ans + C(nn, mm)) * inv[2] % mod;
        }
        while (mm < a[i].m) {
            mm++;
            ans = (ans + C(nn, mm)) % mod;
        }
        while (mm > a[i].m) {
            ans = (ans - C(nn, mm) + mod) % mod;
            mm--;
        }
        a[i].ans = ans;
    }
    sort(a + 1, a + 1 + n,
         [](const Node& A, const Node& B) { return A.id < B.id; });
    for (int i = 1; i <= n; i++) {
        printf("%lld\n", a[i].ans);
    }
}

D. Nothing is Impossible

出题人锅了,虽然后面改了题意,但也不想再看了...

贴一发当时AC的代码吧

//ybmj
#include<bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define lson_len (len - (len >> 1))
#define rson_len (len >> 1)
#define pb(x) push_back(x)
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const int maxn = 105;
struct P{
    int x,y;
    bool operator < (const P& A) const{
        return  y < A.y;
    }
};
P a[maxn];
int main(){
    // /*
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif
    // */
    std::ios::sync_with_stdio(false);
    int T;
    scanf("%d",&T);
    while(T--){
        ll n, m;
        scanf("%lld%lld",&n,&m);
        int ans = 0;
        for(int i=0;i<n;i++){
            scanf("%d%d",&a[i].x, &a[i].y);
            if(a[i].y == 0 && a[i].x != 0) ans++;
        }
        sort(a,a+n);
        ll foo = 1;
        for(int i=0;i<n;i++){
            if(a[i].x == 0 || a[i].y == 0) continue;
            foo *= (a[i].y + 1);
            if(foo > m) break;
            ans++;
            
        }
        printf("%d\n",ans);
    }
}

E. Matrix from Arrays

题意

int cursor = 0;
for (int i = 0; ; ++i) {
    for (int j = 0; j <= i; ++j) { 
        M[j][i - j] = A[cursor];
        cursor = (cursor + 1) % L;
    }
}

用上述方法构造一个无限大的矩阵,然后若干个查询,每次查询求子矩阵的和。

分析

比赛时是打表发现了规律,即对于L为奇数,那么它纵向和横向都存在循环节,且循环节长度为L。对于L为偶数,
同样存在循环节,只不过长度为2L。

然后就可以预处理前缀和,然后计算子矩阵的和。

小技巧是可以把循环节长度统一定为2L,这样就不用分类讨论了。

题解里面推导了一下

$M[i][k] = A[\frac{(1+i+k)(i+k)}{2} + 2 \quad mod \quad L] = M[i+2L][k] = M[i][k+2L]$

代码

// ybmj
#include <bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define lson_len (len - (len >> 1))
#define rson_len (len >> 1)
#define pb(x) push_back(x)
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define first fi
#define second se
#define my_unique(a) a.resize(distance(a.begin(), unique(a.begin(), a.end())))
#define my_sort_unique(c) (sort(c.begin(), c.end())), my_unique(c)
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const int maxn = 150;
int A[30];
int M[maxn][maxn];
ll sum[maxn][maxn];
void init(int L) {
    int sz = 100, p = 0;

    for (int i = 0; i < sz; i++) {
        for (int k = 0; k <= i; k++) {
            M[k][i - k] = A[p];
            p = (p + 1) % L;
        }
    }
    for (int i = 1; i <= L * 2; i++) {
        for (int k = 1; k <= L * 2; k++) {
            sum[i][k] = M[i - 1][k - 1] + sum[i - 1][k] + sum[i][k - 1] -
                        sum[i - 1][k - 1];
        }
    }
}

ll solve(int x, int y, int L) {
    ll ret = 0;
    ret += sum[L][L] * (x / L) * (y / L);
    ret += sum[L][y % L] * (x / L);
    ret += sum[x % L][L] * (y / L);
    ret += sum[x % L][y % L];
    return ret;
}
int main() {
// /*
#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
#endif
    // */
    std::ios::sync_with_stdio(false);
    int T;
    scanf("%d", &T);
    while (T--) {
        int L, Q;
        scanf("%d", &L);
        for (int i = 0; i < L; i++) scanf("%d", A + i);
        init(L);
        L <<= 1;
        scanf("%d", &Q);
        int x0, y0, x1, y1;
        while (Q--) {
            scanf("%d%d%d%d", &x0, &y0, &x1, &y1);
            x0++, y0++, x1++, y1++;
            ll ans = 0;
            ans += solve(x1, y1, L);
            ans -= solve(x1, y0 - 1, L);
            ans -= solve(x0 - 1, y1, L);
            ans += solve(x0 - 1, y0 - 1, L);
            printf("%lld\n", ans);
        }
    }
}
最后修改:2020 年 07 月 31 日 09 : 11 PM