2018川大校赛补

SCU-4581

由于内存限制,对$v < 1e6$做普通背包,对$n < 20$做容斥即可
想到了容斥居然想不出组合数公式

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int BUFFER_MAX_SIZE = 100000;
struct Quick_In {
char buf[BUFFER_MAX_SIZE], *ps = buf, *pe = buf + 1;
inline void InNext() {
if (++ps == pe)
pe = (ps = buf) + fread(buf, sizeof(char), sizeof(buf) / sizeof(char), stdin);
}
template<class T>
inline bool operator()(T &number) {
number = 0;
T f = 1;
bool vis_point = 0;
if (ps == pe) return false; //EOF
do {
InNext();
if ('-' == *ps) f = -1;
} while (ps != pe && !isdigit(*ps));
if (ps == pe) return false; //EOF
do {
if((*ps) == '.') vis_point = 1;
else {
number = number * 10 + *ps - 48;
if(vis_point) f *= 0.1;
}
InNext();
} while (ps != pe && (isdigit(*ps) || (*ps) == '.'));
number *= f;
return true;
}
} In;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
int add(int x, int y) {
x += y;
if(x >= mod) x -= mod;
return x;
}
int mul(int x, int y) {
LL z = 1LL * x * y;
return z - z / mod * mod;
}
int powt(int x, int y) {
int r = 1;
while(y) {
if(y & 1) r = mul(r, x);
x = mul(x, x);
y >>= 1;
}
return r;
}
int f[maxn], a[20];
int C(int n, int m) {
if(m > n) return 0;
int res = 1;
for(int i = 0;i < m; i++) res = mul(res, mul(n - i, powt(i + 1, mod - 2)));
return res;
}
void solve() {
int n, v, w, c, i, j, res;
In(n);
In(v);
if(v < maxn) {
for(i = 0; i <= v; i++) f[v] = 0;
f[0] = 1;
for(i = 0; i < n; i++) {
In(c);
for(j = v - c + 1, res = 0; j <= v; j++) res = add(res, f[j]);
for(j = v; j > 0; j--) {
res = add(res, mod - f[j]);
if(j >= c) res = add(res, f[j - c]);
f[j] = add(f[j], res);
}
}
printf("%d\n", f[v]);
} else {
for(i = 0;i < n; i++) In(a[i]);
for(i = res = 0;i < (1 << n); i++) {
for(j = c = 0, w = v;j < n; j++) {
if((i >> j) & 1) {
w -= a[j] + 1;
c++;
}
}
if(c & 1) res = add(res, mod - C(w + n - 1, n - 1));
else res = add(res, C(w + n - 1, n - 1));
}
printf("%d\n", res);
}
}
int main() {
#ifdef CX_TEST
//freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
int t;
scanf("%d", &t);
while(t--) solve();
return 0;
}

SCU-4589

题意:求质数的$k$次方前缀和
一种类似欧拉筛法的基本应用吧
复杂度是$O(k * n^{3/4}/logn)$的
这个手写$k$次方自然数前缀和真恶心

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int maxn = 1e5 + 5;
int mod, k;
int add(int x, int y) {
x += y;
if(x >= mod) x -= mod;
return x;
}
int mul(int x, int y) {
LL z = 1LL * x * y;
return z - z / mod * mod;
}
LL mul(LL a, LL b, LL m) {
LL r = (a * b - (LL)(((long double)a * b) / m) * m);
r = r - r / m * m;
if(r < 0) r += m;
return r;
}
int powt(int x, int y) {
int r = 1;
while(y) {
if(y & 1) r = mul(r, x);
x = mul(x, x);
y >>= 1;
}
return r;
}
int fg[maxn], pri[maxn];
LL sum[maxn];
int cnt = 0;
void GetPrime() {
for (int i = 2; i < maxn; ++i) {
if (!fg[i]) pri[cnt++] = i;
for (int j = 0; j < cnt && pri[j] * i < maxn; ++j) {
fg[pri[j] * i] = 1;
if (i % pri[j] == 0) break;
}
}
}
int S(int n) {
int res;
if(k == 0) res = n % mod;
else if(k == 1) res = 1LL * n * (n + 1) / 2 % mod;
else if(k == 2) {
LL m = 1LL * mod * 6;
res = mul(mul(n, n + 1, m), 2 * n + 1, m) / 6;
} else if(k == 3) {
LL m = 1LL * mod * 4;
res = mul(mul(n, n + 1, m), mul(n, n + 1, m), m) / 4;
} else if(k == 4) {
LL m = 1LL * mod * 30;
LL d = mul(6LL * n + 9, n, m);
d = mul(d + 1, n, m) + m - 1;
res = mul(d, mul(n, n + 1, m), m) / 30;
} else if(k == 5) {
LL m = 1LL * mod * 12;
LL d = mul(2LL * n + 4, n, m);
d = mul(d + 1, n, m) + m - 1;
res = mul(d, mul(mul(n, n, m), n + 1, m), m) / 12;
} else if(k == 6) {
LL m = 1LL * mod * 42;
LL d = mul(6LL * n + 15, n, m);
d = mul(d + 6, n, m);
d = mul(d + m - 6, n, m);
d = mul(d + m - 1, n, m) + 1;
res = mul(d, mul(n, n + 1, m), m) / 42;
} else if(k == 7) {
LL m = 1LL * mod * 24;
LL d = mul(3LL * n + 9, n, m);
d = mul(d + 5, n, m);
d = mul(d + m - 5, n, m);
d = mul(d + m - 2, n, m) + 2;
res = mul(d, mul(mul(n, n, m), n + 1, m), m) / 24;
} else if(k == 8) {
LL m = 1LL * mod * 90;
LL d = mul(10LL * n + 35, n, m);
d = mul(d + 25, n, m);
d = mul(d + m - 25, n, m);
d = mul(d + m - 17, n, m);
d = mul(d + 17, n, m);
d = mul(d + 3, n, m) + m - 3;
res = mul(d, mul(n, n + 1, m), m) / 90;
} else if(k == 9) {
LL m = 1LL * mod * 20;
LL d = mul(2LL * n + 8, n, m);
d = mul(d + 7, n, m);
d = mul(d + m - 7, n, m);
d = mul(d + m - 7, n, m);
d = mul(d + 7, n, m);
d = mul(d + 3, n, m) + m - 3;
res = mul(d, mul(mul(n, n, m), n + 1, m), m) / 20;
} else {
LL m = 1LL * mod * 66;
LL d = mul(6LL * n + 27, n, m);
d = mul(d + 28, n, m);
d = mul(d + m - 28, n, m);
d = mul(d + m - 38, n, m);
d = mul(d + 38, n, m);
d = mul(d + 28, n, m);
d = mul(d + m - 28, n, m);
d = mul(d + m - 5, n, m) + 5;
res = mul(d, mul(n, n + 1, m), m) / 66;
}
return add(res, mod - 1);
}
LL fa[maxn], fb[maxn];
void solve() {
LL i, r, n;
scanf("%lld%d%d", &n, &k, &mod);
for(r = 1; 1LL * r * r <= n; r++) fa[r] = S(r);
for(i = 1; i < r; i++) fb[i] = S(n / i);
for(LL p = 2; p < r; p++) {
if(!fg[p]) {
int pw = powt(p, k);
for(i = 1; i <= min(r - 1, n / p / p); i++) {
if(p * i < r) fb[i] = add(fb[i], mod - mul(pw, add(fb[i * p], mod - fa[p - 1])));
else fb[i] = add(fb[i], mod - mul(pw, add(fa[n / p / i], mod - fa[p - 1])));
}
for(i = r - 1; i >= p * p; i--) fa[i] = add(fa[i], mod - mul(pw, add(fa[i / p], mod - fa[p - 1])));
}
}
printf("%lld\n", fb[1]);
}
int main() {
#ifdef CX_TEST
freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
int t;
GetPrime();
scanf("%d", &t);
while(t--) solve();
return 0;
}