九月题目泛做总结。
maki美如画中仙!
Keywords Binary Indexed Tree, Matrix Multiplication, Mathematics , Matrix Hash, Memorization&Search, KMP
Table of Contents Keywords BZOJ 2743 采花 Description Solution BZOJ 2326 数学作业 Description Solution BZOJ 2721 [Violet 5]樱花 Description Solution BZOJ 1567 Blue Mary的战略地图 Description Solution BZOJ 1079 着色方案 Description Solution BZOJ 1511 OKR Description Solution BZOJ 2743 采花 Description 与HH的项链不同的是, 这次要统计至少出现2次之类的数量.
能够成功采花的条件是, 之前采过同样的花, 在区间内有可预见的同种花.
求颜色种类数.
Solution 同样记录向后第一个同色出现位置, 对答案排序, 离线作答.
枚举左端点, 每当我们要离开一个位置时, 由于她的下一个位置不再有保证, 所以树状数组中加入 $-1$. 她下一个位置的下一个位置此时有了保障, 树状数组中加入 $1$.
求一个区间和就是答案.
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 #include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <cctype> using namespace std ;const int maxn = 2e+6 + 5 ;struct node { int l, r, id; bool operator < (const node &rhs) const { return l < rhs.l; } }t[maxn]; int n, m, c, a[maxn], lst[maxn], nxt[maxn];int b[maxn], ans[maxn];inline void add (int x, int v) for (; x <= n; x += (x & -x)) b[x] += v;}inline int query (int x) int ret = 0 ; for (;x;x-=(x&-x))ret+=b[x]; return ret;}inline int rd () register int x = 0 ; char c = getchar(); while (!isdigit (c)) c = getchar(); while (isdigit (c)) x = x * 10 + (c ^ 48 ), c = getchar(); return x; } int main () n = rd(); c = rd(); m = rd(); for (int i = 1 ; i <= n; ++i) a[i] = rd(); for (int i = n; i; --i) nxt[i] = lst[a[i]], lst[a[i]] = i; for (int i = 1 ; i <= c; ++i) if (nxt[lst[i]]) add(nxt[lst[i]], 1 ); for (int i = 1 ; i <= m; ++i) t[i].l = rd(), t[i].r = rd(), t[i].id = i; sort(t + 1 , t + 1 + m); int ptr = 1 ; for (int i = 1 ; i <= m; ++i) { while (ptr < t[i].l) { if (nxt[ptr]) add(nxt[ptr], -1 ); if (nxt[nxt[ptr]]) add(nxt[nxt[ptr]], 1 ); ptr++; } ans[t[i].id] = query(t[i].r) - query(t[i].l - 1 ); } for (int i = 1 ; i <= m; ++i) printf ("%d\n" , ans[i]); return 0 ; }
BZOJ 2326 数学作业 Description 定义一个操作 $Concatenate(1\ldots N)\; Mod \; M = \overline{1234\ldots N}\;Mod\;M$.
$1 \le N \le 10^{18}, \, 1\le M \le 10^9$.
Solution $N$ 太大了. 一看过去是矩乘, 但是怎么转移呢?
考虑分段在每个长度下转移, 由于每次增加的长度固定, 就比较好想了, 而且额外的复杂度不多. 套了个$lg$.
转移就是:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 $ \begin{pmatrix} f[n] & n & 1 \end{pmatrix} = \begin{pamtrix} f[n-1] & n-1 & 1 \end{pmatrix} \begin{pmatrix} 10^k & 0 & 0\\ 1 & 1 & 0\\ 1 & 1 & 0\\ \end{pmatrix} $
枚举位数, 一直做到 $N$ 就好了.
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 #include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std ;typedef unsigned long long ll;ll n; ll mod; inline ll quick_mul (ll base, ll index) ll ret = 0 ; while (index) { if (index & 1 ) ret = (ret + base) % mod; index >>= 1 ; base = (base + base) % mod; } return ret; } struct matrix { ll a[5 ][5 ]; int N, M; matrix(){memset (a, 0 , sizeof a);} ll& operator () (int x, int y) { return a[x][y]; } matrix operator * (matrix rhs) { matrix ret; ret.N = N; ret.M = rhs.M; for (int k = 1 ; k <= M; ++k) for (int i = 1 ; i <= N; ++i) for (int j = 1 ; j <= rhs.M; ++j) ret(i,j) = (ret(i, j) + quick_mul(a[i][k], rhs(k, j))) % mod; return ret; } }ans, mtr; inline void quick_power (matrix &res, matrix base, ll index) while (index) { if (index & 1 ) res = res * base; index >>= 1 ; base = base * base; } } inline void solve (ll k, ll term) mtr = matrix(); mtr.N = mtr.M = 3 ; ll index = term - k/10 + 1 ; mtr(1 ,1 ) = k; mtr(2 ,1 ) = mtr(2 ,2 ) = mtr(3 ,1 ) = mtr(3 ,2 ) = mtr(3 ,3 ) = 1 ; quick_power(ans, mtr, index); } int main () scanf ("%llu%llu" , &n, &mod); ans.N = 1 ; ans.M = 3 ; ans(1 ,3 ) = 1 ; ll t = 10 ; while (t <= n) solve(t, t - 1 ), t *= 10 ; solve(t, n); printf ("%llu\n" , ans(1 ,1 )); return 0 ; }
BZOJ 2721 [Violet 5]樱花 Description 求满足 $\frac{1}{x} + \frac{1}{y} = \frac{1}{N!} $ 的正整数解组数.
Solution 推式子什么的, Bouvardia很需要呢.
$yN! + xN! = xy,$
$xy - (x+y)N! = 0,$
$xy - (x+y)N! + {N!}^2 = {N!}^2,$
$(x - N!)(y - N!) = N!^2.$
为了使结果是正整数, $x,\, y$ 也一定是正整数, 保证合法.
那么就转化成求有多少组$\,A,\,B$, 满足$AB = N!^2$ 的问题了.
考虑求出素因子指数, 这时只要确定$A$的一个指数序列, $B$也就能对应求出, 乘法原理就可以求出解的组数.
筛出素数, $N!$ 有一个这样的性质:
对于一个数 $k$, 一定有 $N!$ 中 $k$ 的指数 $\begin{align}q = \sum_{i = 0}^{\infty}\lfloor \frac{N}{k^i} \rfloor \end{align}$.
这样就可以求了, 因为是平方, 记得对求出的指数乘个2.
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 #include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> #include <bitset> using namespace std ;typedef long long ll;const int maxn = 1e+6 + 5 ;const int maxp = 4e+5 + 5 ;const int p = 1e+9 + 7 ;bitset <maxn> ispr;int n, pr[maxp], ind[maxp], mindiv[maxn], cnt;inline void euler () ispr.set (); for (int i = 2 ; i < maxn; ++i) { if (ispr[i]) pr[++cnt] = i; for (int j = 1 ; j <= cnt && i * pr[j] < maxn; ++j) { ispr.reset(i * pr[j]); if (!(i % pr[j])) break ; } } } int main () euler(); scanf ("%d" , &n); for (int i = 1 ; i <= cnt && pr[i] <= n; ++i) for (ll t = pr[i]; t <= (ll)n; t *= (ll)pr[i]) ind[i] += n/t; for (int i = 1 ; i <= cnt && pr[i] <= n; ++i) ind[i] *= 2 ; ll ans = 1 ; for (int i = 1 ; i <= cnt && pr[i] <= n; ++i) ans = (ans * (ind[i] + 1 )) % p; printf ("%lld\n" , ans); return 0 ; }
BZOJ 1567 Blue Mary的战略地图 Description 求两个矩阵中最大的完全相同的正方形子矩阵.
Solution 直接求不好求, 转验证. 二分答案 + 矩阵哈希.
这是一个板子.
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 #include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std ;typedef unsigned long long ll;const int maxn = 55 ;const int hsh = 2879 ;const int hsh2 = 6277 ;int n, a[55 ][55 ], b[55 ][55 ];ll fa[55 ][55 ], fb[55 ][55 ], R[55 ], arr[2505 ]; ll col (int t_, int x, int y, int l) ll ret = 1 ; for (int i = x; i <= x + l - 1 ; ++i) for (int j = y; j <= y + l - 1 ; ++j) { if (t_) ret = ret * hsh2 + fa[i][y + l - 1 ] - fa[i][y - 1 ]*R[l]; else ret = ret * hsh2 + fb[i][y + l - 1 ] - fb[i][y - 1 ]*R[l]; } return ret; } bool chk (int mid) int tot = 0 ; ll cur; for (int i = 1 ; i <= n - mid + 1 ; ++i) for (int j = 1 ; j <= n - mid + 1 ; ++j) arr[++tot] = col(0 , i, j, mid); sort(arr + 1 , arr + 1 + tot); for (int i = 1 ; i <= n - mid + 1 ; ++i) for (int j = 1 ; j <= n - mid + 1 ; ++j) { cur = col(1 , i, j, mid); if (*lower_bound(arr + 1 , arr + 1 + tot, cur) == cur) return true ; } return false ; } int main () R[0 ] = 1 ; for (int i = 1 ; i <= 50 ; ++i) R[i] = R[i - 1 ] * hsh; scanf ("%d" , &n); for (int i = 1 ; i <= n; ++i) for (int j = 1 ; j <= n; ++j) scanf ("%d" , &a[i][j]); for (int i = 1 ; i <= n; ++i) for (int j = 1 ; j <= n; ++j) scanf ("%d" , &b[i][j]); for (int i = 1 ; i <= n; ++i) { fa[i][0 ] = 1 ; for (int j = 1 ; j <= n; ++j) fa[i][j] = fa[i][j - 1 ] * hsh + a[i][j]; } for (int i = 1 ; i <= n; ++i) { fb[i][0 ] = 1 ; for (int j = 1 ; j <= n; ++j) fb[i][j] = fb[i][j - 1 ] * hsh + b[i][j]; } int l = 1 , r = n, ans; while (l <= r) { int mid = (l + r) >> 1 ; if (chk(mid)) ans = mid, l = mid + 1 ; else r = mid - 1 ; } printf ("%d\n" , ans); return 0 ; }
BZOJ 1079 着色方案 Description 每种颜色可以涂若干格, 求相邻格子颜色各不相同的方案数.
Solution 这题好仙的说……考虑到在一个状态下, 剩余量相同的颜色本质是相同的, 因为在合法情况下, 它们一定可以互换. 所以只要记录各种余量的颜色种类数就好了.
一开始想map动态开状态, 后来又想容斥. Bouvardia还是需要对题目做出准确而简洁的反应呐.
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 #include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std ;typedef long long ll;const int mod = 1e+9 + 7 ;ll f[16 ][16 ][16 ][16 ][16 ][6 ]; int bkt[6 ], k, x;ll dfs (int c1, int c2, int c3, int c4, int c5, int l) if (~f[c1][c2][c3][c4][c5][l]) return f[c1][c2][c3][c4][c5][l]; ll tot = 0 ; if (!(c1 | c2 | c3 | c4 | c5)) return 1 ; if (c1) (tot += (c1 - (l == 2 )) * dfs(c1-1 ,c2,c3,c4,c5,1 )) %= mod; if (c2) (tot += (c2 - (l == 3 )) * dfs(c1+1 ,c2-1 ,c3,c4,c5,2 )) %= mod; if (c3) (tot += (c3 - (l == 4 )) * dfs(c1,c2+1 ,c3-1 ,c4,c5,3 )) %= mod; if (c4) (tot += (c4 - (l == 5 )) * dfs(c1,c2,c3+1 ,c4-1 ,c5,4 )) %= mod; if (c5) (tot += (c5) * dfs(c1,c2,c3,c4+1 ,c5-1 ,5 )) %= mod; return f[c1][c2][c3][c4][c5][l] = tot%mod; } int main () memset (f, -1 , sizeof f); scanf ("%d" , &k); for (int i = 1 ; i <= k; ++i) scanf ("%d" , &x), bkt[x]++; printf ("%lld\n" , dfs(bkt[1 ], bkt[2 ], bkt[3 ], bkt[4 ], bkt[5 ], 0 )); return 0 ; }
BZOJ 1511 OKR Description 给定一个串, 求它的每个前缀, 最大周期是多长.
Solution Bouvardia居然手玩出来了.
观察样例, 再感性理解一下, 其实一直跳nxt到不能再跳为止就是答案.
但这样只能拿到40分.
为了加速跳nxt的过程, 我们每次跳完之后就直接修改nxt到最靠前的位置, 类似网络流中当前弧优化的做法.
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 #include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std ;const int maxn = 1e+6 + 5 ;typedef long long ll;int k, nxt[maxn];ll len; char s[maxn];inline void getnxt () for (int i = 2 ; i <= k; ++i) { int j = nxt[i - 1 ]; while (j && s[j + 1 ] != s[i]) j = nxt[j]; if (s[j + 1 ] == s[i]) nxt[i] = j + 1 ; else nxt[i] = 0 ; } } int main () scanf ("%d" , &k); scanf ("%s" , s + 1 ); getnxt(); for (int i = 1 ; i <= k; ++i) { int j = i; while (nxt[j]) j = nxt[j]; if (nxt[i]) nxt[i] = j; len += (i - j); } printf ("%lld\n" , len); return 0 ; }
