1542C-RND#729-RTG1600
这道题看似恶心实则巧妙，因为如果$f(a)=i$则从$1 \sim (i - 1)$ 的数都是a的因数，即$lcm(1,2,3,\dots,x−1) \mid i$ 所以 所以$f(i) \geq a$的$i$的个数等于 $\frac{n}{lcm(1,2,3,\dots,x−1)}$, 简单容斥可得答案为 $\frac{n}{lcm(1,2,3,\dots,x−1)} - \frac{n}{lcm(1,2,3,\dots,x−1,x)}$
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
|
#include <bits/stdc++.h>
#define For(i, l, r) for (long long i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (long long i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const long long mod = 1e9 + 7;
template<typename LDXIN>
LDXIN read() {
LDXIN s = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
long long gcd(long long a, long long b) {
if (a < b) swap(a, b);
return (b == 0) ? a : gcd(b, a % b);
}
long long lcm(long long a, long long b) {
return b / gcd(a, b) * a;
}
int T;
int main() {
T = read<int>();
while (T--) {
long long n;
n = read<long long>();
long long ans = n * 2;
long long now = 1;
For(i, 3, 42) {
now = lcm(now, i - 1);
ans += n / now;
ans %= mod;
}
printf("%lld\n", ans);
}
return 0;
}
|
1542D-RND#729-RTG2200
又因为没开long long WA 了
这道题可以换种方法思考，统计有多少种$B$中可以有$x$ 。设$dp[i][j]$表示处理到第 $i$ 位，有$j$个数小于当前枚举到的$x$
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
|
#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const int maxn = 1010;
const int mod = 998244353;
#define int int64_t
int dp[maxn][maxn], a[maxn];
int totn;
int32_t main() {
int n;
scanf("%lld", &n);
For(i, 1, n) {
char oper;
getchar();
scanf("%c", &oper);
if (oper == '+') {
scanf("%lld", &a[i]);
totn++;
}
}
int ans = 0;
For(i, 1, n) {
if (a[i] == 0) continue;
Set(dp, 0);
dp[0][0] = 1;
For(pos, 1, n) {
For(num, 0, totn) {
dp[pos][num] = dp[pos - 1][num];
if (pos == i) continue;
if (a[pos] == 0) {
dp[pos][num] += dp[pos - 1][num + 1];
dp[pos][num] %= mod;
if (num == 0 && pos < i) {
dp[pos][num] += dp[pos - 1][num];
dp[pos][num] %= mod;
}
} else {
if (a[pos] > a[i]) {
dp[pos][num] += dp[pos - 1][num];
dp[pos][num] %= mod;
} else {
if (a[pos] < a[i]) {
dp[pos][num] += dp[pos - 1][num - 1];
dp[pos][num] %= mod;
} else {
if (pos > i) {
dp[pos][num] += dp[pos - 1][num];
dp[pos][num] %= mod;
} else {
dp[pos][num] += dp[pos - 1][num - 1];
dp[pos][num] %= mod;
}
}
}
}
}
}
For(j, 0, n) {
ans += a[i] * dp[n][j];
ans %= mod;
}
}
cout << ans << endl;
return 0;
}
|