这里记录$\texttt{little_sun}$的$\texttt{FJWC2020}$之旅
Day 1 1 Life 1.1 简要题意 一个$n$个点的有向图，每个点有颜色，部分点的颜色已经确定
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}$方程组:
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)$
于是我们就可以不记$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 ] * 2l l) % 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] * 1l l * (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] * 1l l * (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] * 1l l * (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] * 1l l * (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 ] * 2l l) % 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] * 1l l * 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))) { if ((!(t & 2 )) || c[s] + c[t] < c[s | t]) continue ; ans = sum(ans, ((-1l l * 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$的时候，答案会增加:
其中$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 ; }