Reflection
暴露出的问题是独立思考的能力不足，数学的基础不劳，D 的能力有亿点弱.
主要就是思考能力欠缺，十分欠缺，以后多 VP 一点比赛吧.
个人感觉难度：T3 > T4 > T2 > T1，码力考察小，思考量也不是很大（但虐死我足够了）.
不过思考能力有着明显的进步，这是好事，而且做题太少是不够的，以后要多做题.
inv[i] = (p - p / i) * inv[i % p] % p;
Solution
T1
会，不写了.
T2
看到一个对着一个图进行修改的东西直接上去分层图就行了，这个方法一定要掌握.
然后发现这是一个 01 最短路，然后我们上去 01BFS 即可解决问题.
Code 很简单，不写了.
T3
T3，看到整除考虑用质因子去思考.
有两种方法，但是本质是一样的.
法一
这个方法需要 da♂rk 力打表找规律，并且思路有一点阴间，更推荐法二.
先考虑简单的问题，假如我们只用一个质数的 $i$ 次幂作为最后的结尾的数的数列有多少个.
设 $dp_{i, j}$ 表示用 $i$ 次方，长度为 $j$ 的最后一个数列可以被 $p^i$ 表示的数列的个数.
andy_lz 是真强，这种逆天的状态都能想出来.
定住最后的 $a_j$，我们来思考如何递推：
- 当$a_{j - 1} = p^i$ 的时候，发现定住了，那么这时候的数列数就只能是 $dp_{i, j - 1}$，因为数列本质上没有变化.
- 当 $a_{j - 1} \ne p^i$ 的时候，发现这和 $a_{j} = p^{i - 1}$ 的情况下的数列是一样的.
然后我们得到递推式：
$$
dp_{i, j} = dp_{i - 1, j} + dp_{i, j - 1}
$$
现在我们处理好了固定次幂下的数列个数，考虑下一步：如何扩展到多个质因子的次幂相乘的结果？
发现对于同样的 $i$ 次幂，数列的个数是固定的，无论使用哪一个质因子做底数.（当这个指数在值域范围内的时候.）
那么我们就可以直接考虑值域内的每一个数，它最终可以贡献出多少贡献.
我们求完了 $i$ 次幂，然后我们直接考虑把 $x$ 这个数做结尾会贡献多少的数，而且它还会被不同的分解.
假如 $x = a^i \times b^j$ 的话：
以 $x$ 结尾的数的数列个数就是 $dp_{i, n} \times dp_{j, n}$，因为这样肯定最后能将 $x$ 乘出来，并且前边都是满足条件的数列.
然后我们就可以对于每一个数，看一下它可以分解为某个质因子的多少的幂次方，然后乘上对应的答案数，最后把每个数的贡献总和加到一起，这样就解决了这个问题.
Code
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
| #include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
ll rd() {
ll x = 0, w = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') w = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + (c - '0');
c = getchar();
}
return x * w;
}
const int N = 2e5 + 5;
const long long mod = 998244353;
ll dp[25][N];
int n, m;
ll sum[N], ans;
int tot;
ll pr[N];
bool np[N];
int main() {
n = rd(), m = rd();
for(int i = 1; i <= n; ++i)
dp[0][i] = 1;
for(int i = 1; i <= 20; ++i)
for(int j = 1; j <= n; ++j)
dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % mod;
for(int i = 2; i * i <= m; ++i)
if(!np[i]) {
pr[++tot] = i;
for(int j = i * 2; j * j <= m; j += i)
np[j] = 1;
}
for(int i = 1; i <= m; ++i)
sum[i] = 1;
for(int i = 2; i <= m; ++i) {
int tmp = i, cnt = 0;
for(int j = 1; tmp > 1 && j <= tot; ++j) {
cnt = 0;
while( !(tmp % pr[j] ) )
tmp /= pr[j], ++cnt;
sum[i] = (sum[i] * dp[cnt][n]) % mod;
}
if(tmp > 1)
sum[i] = (sum[i] * dp[1][n]) % mod;
}
for(int i = 1; i <= m; ++i)
ans = (ans + sum[i]) % mod;
printf("%lld", ans);
fclose(stdin);
fclose(stdout);
return 0;
}
|
法二
想要达到互质的效果，我们不妨也考虑最后的数是哪一个数.
最后的数肯定可以分解为一个算术基本定理的形式，我们用这个做一点事情：
若干个质因子相乘，我们将这些质因子随机地放在前面的几个位置上，这是一个组合数问题，然后我们只需要将这些数从头到尾乘过来，不难满足题目要求.
然后我们只需要处理组合数，然后处理逆元，然后做完了.
这个思路还是比较好推的，更推荐这个做法.
Code
PS：此为 L_ndyz 的代码，博主懒得自己写一份了（，声明一下版权.
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
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<cstring>
#include<set>
#include<cmath>
#define int long long
using namespace std;
int n,m;
int p=998244353,ans=0;
long long inv[2000100],A[2000100];
long long C(int x,int y)
{
if(x>y) return 0;
return A[y]*inv[x]%p*inv[y-x]%p;
}
void sol(int now)
{
int sum=1;
for(int i=2;i*i<=now;i++)
{
if(now%i==0)
{
int cnt=0;
while(now%i==0)
{
now/=i;cnt++;
}
sum=sum*C(n-1,cnt+n-1)%p;
}
}
if(now>1)
{
int cnt=1;
sum=sum*C(n-1,cnt+n-1)%p;
}
ans=(ans+sum)%p;
}
signed main()
{
cin>>n>>m;
A[0]=A[1]=inv[0]=inv[1]=1;
for(int i=2;i<=n*5;i++)
{
inv[i]=(p-p/i)*inv[p%i]%p;
}
for(int i=2;i<=n*5;i++)
{
A[i]=(A[i-1]*i)%p;inv[i]=(inv[i-1]*inv[i])%p;
}
for(int i=1;i<=m;i++)
{
sol(i);
}
cout<<ans;
fclose(stdin);
fclose(stdout);
return 0;
}
|
T4
拿到异或，肯定是要拆位考虑的.
想要总和为 $m$，并且每一个二进制位上的 1 的个数都为偶数，不妨按照每一个二进制位考虑，这样能够很方便地保证偶数的限制.
因为一个二进制位会对应 $n$ 个下标位置，而这些下标位置我们是可以随意摆放的，也就是从 $n$ 个物品中选择 $i$ 个物品，这是一个组合数问题，使用杨辉三角 $\mathcal{O}(n^2)$ 即可处理组合数.
然后我们就可以快乐地开搜，然后我们接一个记忆化上去，这样就可以快速地解决这个问题了.
Code
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
| #include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
ll rd() {
ll x = 0, w = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') w = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + (c - '0');
c = getchar();
}
return x * w;
}
const int N = 5005;
const ll mod = 998244353;
ll dp[25][N];
ll n, m, C[N][N];
ll dfs(ll pos, ll res) {
if(dp[pos][res]) return dp[pos][res];
if(pos == 0) return dp[pos][res] = C[n][res];
for(ll i = 0; (1 << pos) * i <= res; i += 2)
dp[pos][res] = (dp[pos][res] + dfs(pos - 1, res - (1 << pos) * i) % mod * C[n][i] % mod) % mod;
return dp[pos][res];
}
int main() {
n = rd(), m = rd();
if(m % 2) printf("0");
else {
C[0][0] = 1;
for(int i = 1; i <= n; ++i) {
C[i][0] = 1;
for(int j = 1; j <= i; ++j)
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
}
printf("%lld\n", dfs(19, m));
}
return 0;
}
|
Somthing Else
这次考试是我安排的.题目是我选的，但我不知道题目的具体内容.所以为什么 Ptilopsis_w 一个学图论的会出两个数学题啊.后来知道被骗了，这是 Jekyll_Y 的题.