2018hdu多校第四场

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的情况出现。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
// 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的代码吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//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

题意

1
2
3
4
5
6
7
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]$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
// 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);
}
}
}
Thank you for your support!