FJWC2020 小记

这里记录$\texttt{little_sun}$的$\texttt{FJWC2020}$之旅

Day 1

1 Life

1.1 简要题意

一个$n$个点的有向图,每个点有颜色,部分点的颜色已经确定
定义一条任意相邻点不同色的路径为交错路径
为所有颜色未定的点确定颜色,并为所有$1 \leq i < j \leq n$,确定图上从$i$到$j$的有向边是否存在
求有多少种方案使得该图交错路径的条数为奇数,对大质数取模
$1\leq n \leq 2 \times 10^5$

1.2 分析

我们设$g_i$表示以$i$结尾的交错路径条数,这样我们有了这样一个$\texttt{dp}$思路:

设$f[i][j][k][h]$表示前$i$个点,有$j$个黑点,有$k$个白点满足他的$g$为奇数,且这$i$个点的$g$之和的奇偶性为$h$的方案数

我们发现如果$i+1$是黑点的话那么只有那$k$个白点会对$g_{i+1}$的奇偶性产生影响,故只要考虑这些点的子集与$i+1$的连边的方案数就好了,白色同理

又因为这些点在计算中都相当于等价的,于是我们只要考虑这些点的子集大小的奇偶性即可

设$calc(x, y)$表示一个大小为$x$的集合取大小奇偶性为$y$的集合的方案数,则我们有了如下一个$\texttt{dp}$方程组:
1.$f[i+1][j][k][h]+=f[i][j][k][h] \times calc(k, 1) \times 2^{i-k} $

2.$f[i+1][j+1][k][h \oplus 1]+=f[i][j][k][h] \times calc(k, 0) \times 2^{i-k}$

3.$f[i+1][j][k][h]+=f[i][j][k][h] \times calc(j, 1) \times 2^{i-j}$

4.$f[i+1][j][k+1][h \oplus 1]+=f[i][j][k][h] \times calc(j, 0) \times 2^{i-j} $

要注意的是,若$i+1$被钦定为黑色则$3,4$转移不可取,白色同理,复杂度$O(n^3)$

我们发现:

$calc(k, 0)\times2^{i-k}=(k \; ? \; 2^{i-1} : 2^i)$
$calc(k, 1)\times2^{i-k}=(k \; ? \; 2^{i-1} : 0)$

于是我们就可以不记$j, k$的值了,改记满足条件的黑白点的存在性,方程变成$f[i][0/1][0/1][0/1]$, 最后的$ans=\sum_{j,k \in {0,1}} f[n][j][k][1]$

1.3 代码

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
#include <bits/stdc++.h>

#define R register
#define ll long long
#define sum(a, b, mod) (((a) + (b)) % mod)

const int MaxN = 5e5 + 10;
const int mod = 998244353;

int f[MaxN][2][2][2];
int n, m, col[MaxN], pow2[MaxN];

inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while (ch > '9' || ch < '0')
{
if (ch == '-')
f = 0;
ch = getchar();
}
while (ch <= '9' && ch >= '0')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return f ? x : (-x);
}

int main()
{
n = read(), pow2[0] = 1;
for (int i = 1; i <= n; i++)
col[i] = read(), pow2[i] = (pow2[i - 1] * 2ll) % mod;
f[0][0][0][0] = 1;
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= 1; j++)
{
for (int k = 0; k <= 1; k++)
{
for (int h = 0; h <= 1; h++)
{
if (col[i + 1] != 1)
{
f[i + 1][j][k][h] = sum(f[i + 1][j][k][h], f[i][j][k][h] * 1ll * (k ? pow2[i - 1] : 0), mod);
f[i + 1][j | 1][k][h ^ 1] = sum(f[i + 1][j | 1][k][h ^ 1], f[i][j][k][h] * 1ll * (k ? pow2[i - 1] : pow2[i]), mod);
}
if (col[i + 1] != 0)
{
f[i + 1][j][k][h] = sum(f[i + 1][j][k][h], f[i][j][k][h] * 1ll * (j ? pow2[i - 1] : 0), mod);
f[i + 1][j][k | 1][h ^ 1] = sum(f[i + 1][j][k | 1][h ^ 1], f[i][j][k][h] * 1ll * (j ? pow2[i - 1] : pow2[i]), mod);
}
}
}
}
}
int ans = 0;
for (int j = 0; j <= 1; j++)
for (int k = 0; k <= 1; k++)
ans = sum(ans, f[n][j][k][1], mod);
printf("%d\n", ans);
return 0;
}

2 Winner

2.1 简要题意

给定一个$n$个点$m$条边的无向图

求给所有边定向使得$1$和$2$可以到达同一个点的方案数

$1 \leq n \leq 15, 1 \leq n \leq \frac{n \times (n - 1)}{2}$

2.2 分析

发现正着做很难搞,考虑用总数减去不合法的数目

设$1$能到达的点集为$S$, $2$能到达的点集为$T$,则不合法的方案数就是$S \cap T = \emptyset$的方案数

设$f_S$表示对点集$S$的导出子图中的边定向能使得$1$能到达$S$内所有节点的方案数$(1 \in S)$,$g_T$表示$2$的类似东西

那么枚举$S,T$如果没有边横跨$S,T$,则这两个点集内部的定向方案数为$f_S \times g_T$

而在$S,T$之外,如果有一条边横跨$S \cup T$内外,则这条边只能从$S \cup T$内连到$S \cup T$外,否则这条边可以随便连,于是现在就可以算出答案了,由于$S \cap T = \emptyset$,所以时间复杂度$O(3 ^ n)$

现在我们考虑怎么计算$f,g$,同样考虑用总数减去不合法的数目,对于集合$S$,总数显然是$2^{S的导出子图边数}$

枚举$S$的真子集$T$,考虑只能到$T$的方案数,则点集$T$内部的方案数显然为$f_T$,外部的方案数为$2^{S-T的导出子图边数}$, 对于横跨$T$与$S-T$的边,显然只能从$S-T$连到$T$,于是这时扣掉的方案数为$f_T*2^{S-T的导出子图边数}$,由于枚举子集,时间复杂度$O(3^n)$

2.3 代码

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 R register
#define ll long long
#define sum(a, b, mod) (((a) + (b)) % mod)

const int MaxN = 16;
const int mod = 1e9 + 7;

int n, m, id;
int pow2[MaxN * MaxN], gr[MaxN][MaxN], c[1 << MaxN], d[1 << MaxN], f[3][1 << MaxN];

inline int read()
{
int x = 0;
char ch = getchar();
while (ch > '9' || ch < '0')
ch = getchar();
while (ch <= '9' && ch >= '0')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return x;
}

int main()
{
n = read(), m = read(), id = read(), pow2[0] = 1;
for (int i = 1; i <= m; i++)
{
int x = read(), y = read();
++gr[x][y], pow2[i] = (pow2[i - 1] * 2ll) % mod;
}
int lim = (1 << n);
for (int s = 0; s < lim; s++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (gr[i][j])
{
if ((s & (1 << (i - 1))) && (s & (1 << (j - 1))))
c[s] += gr[i][j];
if ((s & (1 << (i - 1))) || (s & (1 << (j - 1))))
d[s] += gr[i][j];
}
for (int id = 1; id <= 2; id++)
{
for (int s = 0; s < lim; s++)
{
if (!(s & (1 << (id - 1))))
continue;
f[id][s] = pow2[c[s]];
for (int t = (s - 1) & s; t; t = (t - 1) & s)
f[id][s] = sum(f[id][s], (-f[id][t] * 1ll * pow2[c[s - t]]) % mod + mod, mod);
}
}
int ans = pow2[m];
for (int s = 0; s < lim; s++)
{
if ((!(s & 1)) || (s & 2))
continue;
for (int t = lim - 1 ^ s; t; t = ((t - 1) & (lim - 1 ^ s)))
{
// printf("%d %d %d\n", s, t, ans);
if ((!(t & 2)) || c[s] + c[t] < c[s | t])
continue;
ans = sum(ans, ((-1ll * f[1][s] * f[2][t]) % mod) * pow2[m - d[s + t]] % mod + mod, mod);
}
}
printf("%d\n", ans);
return 0;
}

3 Brr

咕咕咕

Day 2

1 Building

咕咕咕

2 Bracelet

咕咕咕

3 Number

3.1 简要题意

给定操作数$n$和一个数$k$,实现一个集合$s$,支持插入和删除操作。

每次操作后输出$s$内满足$gcd(s_i, s_j) = k$的$(i,j)$对数

令$z$为集合内出现过的数的最大值,则有$1 \leq n,z \leq 10^5$

3.2 分析

题目可以转化为每次加入/删除一个数,并求这个数和集合内多少数的$\texttt{gcd}=k$

容易发现如果一个数不能被$k$整除,那么这个数一定对答案没有贡献

所以问题又转化为每次加入/删除一个数,并求这个数和集合内多少数的$\texttt{gcd}=1$

考虑容斥,那么发现当加入一个数$x$的时候,答案会增加:
$$
\sum_{d|x}cnt[d] \times mu[d]
$$
其中$cnt[i]$表示$i$的倍数出现过多少次,时间复杂度$O(n \sqrt z)$

3.3 代码

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
#include <bits/stdc++.h>

#define R register
#define ll long long
#define sum(a, b, mod) (((a) + (b)) % mod)

const ll MaxN = 5e5 + 10;

ll n, k, cnt, ans;
ll prime[MaxN], p[MaxN], mu[MaxN], val[MaxN], vis[MaxN];

inline ll read()
{
ll x = 0;
char ch = getchar();
while (ch > '9' || ch < '0')
ch = getchar();
while (ch <= '9' && ch >= '0')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return x;
}

void add(ll x, ll v)
{
for (ll i = 1; i * i <= x; i++)
{
if (x % i == 0)
{
val[i] += v;
if (i * i != x)
val[x / i] += v;
}
}
}

ll query(ll x)
{
ll ret = 0;
for (ll i = 1; i * i <= x; i++)
{
if (x % i == 0)
{
ret += mu[i] * val[i];
if (i * i != x)
ret += mu[x / i] * val[x / i];
}
}
return ret;
}

inline void prework()
{
ll n = 200000;
mu[1] = 1, p[0] = p[1] = 1;
for (ll i = 2; i <= n; i++)
{
if (!p[i])
prime[++cnt] = i, mu[i] = -1;
for (ll j = 1; j <= cnt && i * prime[j] <= n; j++)
{
p[i * prime[j]] = 1;
if (i % prime[j] == 0)
break;
mu[i * prime[j]] = -mu[i];
}
}
}

int main()
{
freopen("number.in", "r", stdin);
freopen("number.out", "w", stdout);
prework();
n = read(), k = read();
while (n--)
{
ll op = read(), x = read();
if (op == 1)
{
if (x % k == 0)
vis[x / k]++, ans += query(x / k), add(x / k, 1);
}
else
{
if (x % k == 0 && vis[x / k])
vis[x / k]--, add(x / k, -1), ans -= query(x / k);
}
printf("%lld\n", ans);
}
return 0;
}

Day 3

咕咕咕

Day 4

1 Hakugai

1.1 简要题意

有一个数列$g_i$满足$g_0=a,g_1=b,g_i=3*g_{i-1}-g_{i-2} \ (i \geq 2)$ ,其中$a,b$是给定的常数

现在我们有一个数列$f_{n,k}$满足$f_{n,0}=n,f_{n,k}=f_{g_n,k-1}$,给定$a,b,n,k,p$,求$f_{n,k}$对$p$取模的结果

$1 \leq n, p \leq 10^9, 0 \le a,b \le p, 0 \le k \leq 100$

1.2 分析

由于$k\le100$,所以我们考虑暴力求循环节,然后用矩阵快速幂暴力计算

我们发现题目中的数列是个二阶常系数递推,写出前几项发现是个斐波那契数列

于是斐波那契数列的循环节就很好求了

设要求斐波那契数列对$p$取模的循环节$f(p)$, 若$p=p_1^{k_1} \times \cdots \times p_m^{k_m}$,(其中$p_i$为$p$的第$i$个质因子)

则有$f(p)= lcm(f(p_i) \times p_i^{k_i-1})$,又当$p_i$是质数的时候,若$p_i \equiv \pm1$,则$f(p_i)=p_i-1$,否则$f(p_i)=2\times(p_i+1)$

现在我们会求循环节了,考虑怎么求题目要求的东西

容易发现我们要求的是$g_{g_{g_{\cdots g_{n}}}}$(嵌套$k$层),那么我们发现:

1.第$1$层求的是$ g_i \; mod \; p$的循环节,循环节为$f(p)$

2.第$2$层求的是$ g_i \; mod \; f(p)$的循环节,循环节为$f(f(p))$

以此类推,故我们只要把该过程迭代$k$遍就好了

1.3 代码

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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
# include <bits/stdc++.h>

# define ll long long
# define R register

const ll MaxN = 1e6 + 10;

struct matrix
{
ll n, m;
ll a[5][5];
matrix(ll x = 0, ll y = 0)
{
n = x, m = y;
memset(a, 0, sizeof(a));
}
};

ll a, b, n, k, mod, cnt, faccnt;
ll prime[MaxN], p[MaxN], fac[1000][20];

ll gcd(ll a, ll b){return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}
ll mul(ll x, ll y, ll p){return x * y - (ll) ((long double) x * y / p) * p;}

ll fast_pow(ll a, ll b, ll mod)
{
ll ret = 1;
while(b)
{
if(b & 1)
ret = mul(ret, a, mod) % mod;
a = mul(a, a, mod) % mod;
b >>= 1;
}
return ret;
}

matrix mul(matrix a, matrix b, ll mod)
{
matrix c(a.n, b.m);
for(int i = 1; i <= a.n; i++)
for(int j = 1; j <= b.m; j++)
for(int k = 1; k <= a.m; k++)
c.a[i][j] = (c.a[i][j] + mul(a.a[i][k], b.a[k][j], mod) % mod + mod) % mod;
return c;
}

matrix I()
{
matrix c(2, 2);
c.a[1][1] = 1;
c.a[2][2] = 1;
return c;
}

matrix pow(matrix a, ll b, ll mod)
{
matrix ret = I();
while(b)
{
if(b & 1)
ret = mul(ret, a, mod);
a = mul(a, a, mod);
b >>= 1;
}
return ret;
}

matrix init1()
{
matrix a(2, 2);
a.a[1][1] = 3, a.a[1][2] = -1;
a.a[2][1] = 1, a.a[2][2] = 0;
return a;
}

matrix init2()
{
matrix c(2, 1);
c.a[1][1] = b;
c.a[2][1] = a;
return c;
}

ll getf(ll x, ll mod)
{
if(x == 0) return a % mod;
if(x == 1) return b % mod;
matrix a = init1(), b = init2(), res = mul(pow(a, x-1, mod), b, mod);
return (res.a[1][1] % mod + mod) % mod;
}

void prework()
{
ll n = 1000000;
p[0] = p[1] = 1;
for(int i = 2; i <= n; i++)
{
if(!p[i])
prime[++cnt] = i;
for(int j = 1; j <= cnt && i * prime[j] <= n; j++)
{
p[i * prime[j]] = 1;
if(i % prime[j] == 0)
break;
}
}
}

void getfac(ll x)
{
ll tmp = x;
for(int i = 1; i <= faccnt + 1; i++)
fac[i][0] = fac[i][1] = 0;faccnt = 0;
for(int i = 1; prime[i] <= tmp / prime[i]; i++)
{
if(tmp % prime[i] == 0)
{
++faccnt;
fac[faccnt][0] = prime[i];
while((tmp % prime[i]) == 0 && tmp != 1)
fac[faccnt][1]++, tmp /= prime[i];
}
}
if(tmp != 1)
{
++faccnt;
fac[faccnt][0] = tmp;
fac[faccnt][1] = 1;
}
}

ll g(ll p)
{
ll num;
(p % 5 == 1 || p % 5 == 4) ? (num = p - 1) : (num = 2 * (p + 1));
return num;
}

std::map<ll, ll> m;

ll getloop(ll n)
{
if(m.find(n) != m.end()) return m[n];
getfac(n);
ll ans = 1;
for(int i = 1; i <= faccnt; i++)
{
ll res = 1;
if(fac[i][0] == 2) res = 3;
else if(fac[i][0] == 3) res = 8;
else if(fac[i][0] == 5) res = 20;
else res = g(fac[i][0]);
for(int j = 1; j < fac[i][1]; j++)
res *= fac[i][0];
ans = lcm(ans, res);
}
return m[n] = ans;
}

int main()
{
freopen("hakugai.in", "r", stdin);
freopen("hakugai.out", "w", stdout);
ll T;
prework();
scanf("%lld", &T);
while(T--)
{
scanf("%lld%lld%lld%lld%lld", &a, &b, &n, &k, &mod);
if(k == 1)
{
printf("%lld\n", getf(n, mod));
continue;
}
ll loop[101] = {mod};
for(int i = 1; i <= k; i++)
loop[i] = getloop(loop[i - 1]);
n %= loop[k];
for(int i = k - 1; ~i; i--)
n = getf(n, loop[i]);
ll ans = n;
printf("%lld\n", ans);
}
return 0;
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×