A. The power of Fibonacci upsolved
求斐波那契数列的\(m\) 次方的前\(n\) 项的和模1e9的值 \((1<=n<=1e9, 1<=m<=1000)\)
首先要知道斐波那契数列模意义下是有循环节的,它的循环节也必定是它的\(m\) 次方的循环节
然后把\(1e9\) 拆成\(2^9*5^9\) , 对\(2^9\) 和\(5^9\) 这两个模数分别找循环节,\(2^9\) 的循环节是768, \(5^9\) 的循环节是7812500
这两个分别求出了然后拼起来就可以得到答案了
ps:为什么快速幂的时候每次把模数(\(2^9\) 或\(5^9\) )传进去的时间是直接把模数钉死为1e9的三倍啊...
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 #include <bits/stdc++.h> using namespace std;const int N = 8e6 + 10 ;const int mod[2 ] = {512 , 125 * 125 * 125 };int f[N];int ans[2 ];int n, m;int qp (int a, int n, int mod = 1000000000 ) { int res = 1 ; while (n) { if (n & 1 ) res = 1LL * res * a % mod; a = 1LL * a * a % mod; n >>= 1 ; } return res; } int main () { scanf ("%d%d" , &n, &m); for (int k = 0 ; k < 2 ; ++k) { f[0 ] = 0 ; f[1 ] = 1 ; int j = 2 ; for (; ; ++j) { f[j] = f[j - 1 ] + f[j - 2 ]; if (f[j] >= mod[k]) f[j] -= mod[k]; if (f[j] == 0 && f[j - 1 ] == 1 ) break ; } for (int i = 0 ; i < j; ++i) { int cnt = n / j + (n % j >= i); ans[k] = (ans[k] + 1LL * cnt * qp (f[i], m)) % mod[k]; } } while (ans[1 ] % mod[0 ] != ans[0 ]) ans[1 ] += mod[1 ]; printf ("%d\n" , ans[1 ]); return 0 ; }
B. Quadratic equation solved at 00:53
队友做的,二次剩余,不会
D. Knapsack Cryptosystem solved at 00:20
\(n\) 个物品,每个物品有重量,你要找到一个子集使得物品的重量和恰好为\(s\) \((1<=n<=36)\) 输入保证有唯一解
折半搜索,先把考虑前一半,二进制状压把它们能组成的所有情况全部丢到\(map\) 里去,然后考虑后一半,每次二进制状压然后去\(map\) 里寻找解
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 #include <bits/stdc++.h> using namespace std;int n, p, q;long long s, a[40 ];int to[(1 << 18 ) + 10 ];map<long long , int > pp; void init () { int msk = 2 ; to[1 ] = 0 ; for (int i = 1 ; i <= 17 ; ++i) { to[msk] = i; msk *= 2 ; } } void print (int maskp, int maskq) { for (int i = 0 ; i < p; ++i) printf ("%d" , 1 & (maskp >> i)); for (int i = 0 ; i < q; ++i) printf ("%d" , 1 & (maskq >> i)); puts ("" ); } int main () { init (); cin >> n >> s; for (int i = 0 ; i < n; ++i) cin >> a[i]; p = n / 2 ; q = n - p; for (int i = 0 ; i < (1 << p); ++i) { long long tmp = 0 ; for (int j = i; j; j -= j & -j) tmp += a[to[j & -j]]; pp[tmp] = i; } for (int i = 0 ; i < (1 << q); ++i) { long long tmp = 0 ; for (int j = i; j; j -= j & -j) tmp += a[to[j & -j] + p]; auto it = pp.lower_bound (s - tmp); if (it->first + tmp == s) { print (it->second, i); return 0 ; } } puts ("-1" ); return 0 ; }
E. All men are brothers solved at 00:49
\(n\) 个人,一开始互相都不认识,\(m\) 次操作,每次会让两个人互相认识,这种认识关系具有传递性和对称性,每次操作后要求输出选择\(4\) 个人互相都不认识的方案数
并查集维护连通块大小即可
考虑合并两个连通块,那么答案会比上一次的答案减少一些,减少的是这两个连通块各选一个,再从外面选不在同一个连通块里的两个的方案数,具体就不写了,看代码(sz指所有连通块大小的平方和)
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 #include <bits/stdc++.h> using namespace std;const int N = 1e5 + 10 ;int n, m, x, y;int fa[N], size[N];long long sz;unsigned long long ans;int find (int x) { return fa[x] == x ? x : find (fa[x]); } void unite (int x, int y) { int fx = find (x), fy = find (y); if (fx != fy) { if (size[fx] < size[fy]) swap (fx, fy); fa[fy] = fx; size[fx] += size[fy]; } } int main () { scanf ("%d%d" , &n, &m); if (n <= 3 ) { for (int i = 0 ; i <= m; ++i) puts ("0" ); return 0 ; } for (int i = 1 ; i <= n; ++i) { fa[i] = i; size[i] = 1 ; } ans = 1ULL * n * (n - 1 ) / 2 * (n - 2 ) / 3 * (n - 3 ) / 4 ; printf ("%llu\n" , ans); sz = n; for (int i = 1 ; i <= m; ++i) { scanf ("%d%d" , &x, &y); if (find (x) == find (y)) { printf ("%llu\n" , ans); continue ; } int sx = size[find (x)], sy = size[find (y)]; ans -= 1ULL * sx * sy * (1ULL * (n - sx - sy) * (n - sx - sy) - (sz - 1LL * sx * sx - 1LL * sy * sy)) / 2 ; sz -= 1LL * sx * sx; sz -= 1LL * sy * sy; sz += 1LL * (sx + sy) * (sx + sy); printf ("%llu\n" , ans); unite (find (x), find (y)); } return 0 ; }
H. Cutting Bamboos solved at 03:11(+2)
有\(n\) 株竹子,每株有高度,\(q\) 次询问,每次询问一个区间\(l, r\) ,给定\(x, y\)
,指的是水平方向切了\(y\) 刀并且每一刀切下来的竹子总量相同且最后一刀高度为\(0\) , 求第\(x\) 刀的高度
首先每一刀切下来的总量相同,那么可以求出第\(x\) 刀到第\(y\) 到切下的总量,然后二分答案,查询当前高度下的竹子总量(小于等于刀的高度的就是竹子本身高度,大于的是刀的高度),那么相当于求区间小于\(k\) 的数的个数以及它们的和,可以用主席树实现,总复杂度\(O(q\log(n)(\log(h) + 50))\) (50是浮点数二分次数,可能不需要这么多)
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 #include <bits/stdc++.h> using namespace std;const int N = 2e5 + 10 ;struct node { int l, r, cnt; long long sum; }Tree[N * 20 ]; int root[N];int cnt;void init () { cnt = 0 ; root[0 ] = 0 ; Tree[0 ].l = Tree[0 ].r = Tree[0 ].cnt = Tree[0 ].sum = 0 ; } void update (int &rt, int l, int r, int num) { Tree[++cnt] = Tree[rt]; rt = cnt; Tree[rt].cnt++; Tree[rt].sum += num; if (l == r) return ; int mid = l + r >> 1 ; if (num <= mid) update (Tree[rt].l, l, mid, num); else update (Tree[rt].r, mid + 1 , r, num); } pair<int , long long > query (int i, int j, int num, int l, int r) { if (l == r) return make_pair (Tree[j].cnt - Tree[i].cnt, Tree[j].sum - Tree[i].sum); int mid = l + r >> 1 ; if (num <= mid) return query (Tree[i].l, Tree[j].l, num, l, mid); pair<int , long long > tmp = query (Tree[i].r, Tree[j].r, num, mid + 1 , r); return make_pair (Tree[Tree[j].l].cnt - Tree[Tree[i].l].cnt + tmp.first, Tree[Tree[j].l].sum - Tree[Tree[i].l].sum + tmp.second); } int n, q, l, r, x, y;int h[N];long long sumh[N];double check (double height) { if (height < 1 ) return (r - l + 1 ) * height; int c; long long s; tie (c, s) = query (root[l - 1 ], root[r], (int )height, 1 , 100000 ); return s + (r - l + 1 - c) * height; } int main () { init (); scanf ("%d%d" , &n, &q); for (int i = 1 ; i <= n; ++i) { scanf ("%d" , &h[i]); root[i] = root[i - 1 ]; update (root[i], 1 , 100000 , h[i]); sumh[i] = sumh[i - 1 ] + h[i]; } while (q--) { scanf ("%d%d%d%d" , &l, &r, &x, &y); int ll = 0 , rr = 1e5 , ans; double tar = (1.0 * y - x) / y * (sumh[r] - sumh[l - 1 ]); while (ll <= rr) { int mid = ll + rr >> 1 ; if (check (mid) <= tar) { ans = mid; ll = mid + 1 ; } else { rr = mid - 1 ; } } double o, lll = ans, rrr = ans + 1 ; for (int _ = 0 ; _ <= 50 ; ++_) { o = (lll + rrr) / 2 ; if (check (o) <= tar) lll = o; else rrr = o; } printf ("%.15f\n" , o); } return 0 ; }
I. KM and M upsolved
给你\(N, M(1<=N<=1e18, 1<=M<=1e11)\) ,求\[\sum\limits_{k=1}^N((kM)\&M) mod (1e9+7)\]
按二进制位每一位考虑,考虑第\(i\) 位,那么一个数\(x\) 的贡献就是\((2^i)\&x\) , 考虑\(x\) 的第\(i\) 位是否为\(1\) ,显然可以用\(\frac x {2^i} - 2 * \frac x {2^{i+1}}\) 表示
那么对于\(N\) 个数,第\(i\) 位为\(1\) 的就是\[\sum \limits_{i=1}^{N} \frac {M * i} {2^i} - 2*\sum \limits_{i=1}^{N} \frac {M * i} {2^{i+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 #include <bits/stdc++.h> using namespace std;using LL = long long ;const int mod = 1e9 + 7 , inv2 = (mod + 1 ) / 2 ;LL n, m, ans; LL calc (LL a, LL b, LL c, LL n) { if (!a) return 0 ; if (a >= c || b >= c) { LL tmp = calc (a % c, b % c, c, n); return (tmp + ((n % mod) * ((n + 1 ) % mod) % mod * inv2 % mod) * ((a / c) % mod) % mod + ((n + 1 ) % mod) * ((b / c) % mod) % mod) % mod; } LL f = ((__int128)a * n + b) / c; return (((n % mod) * (f % mod) % mod - calc (c, c - b - 1 , a, f - 1 )) % mod + mod) % mod; } int main () { cin >> n >> m; for (int i = 0 ; i < 40 ; ++i) if (m >> i & 1 ) { LL res = ((calc (m, 0 , 1LL << i, n) - 2 * calc (m, 0 , 2LL << i, n)) % mod + mod) % mod; ans = (ans + (1LL << i) % mod * res % mod) % mod; } printf ("%lld\n" , ans); return 0 ; }
J. Symmetrical Painting solved at 01:38(+4)
为什么map一直MLE啊.....
二维平面上有n个矩形,每个矩形左下角是\((i - 1, L_i)\) , 右上角是\((i, R_i)\) ,矩形一开始全是黑色,平面不被矩形覆盖的地方是白色,你要把某些黑色区域涂白(一个矩形可以内部颜色不一样),使得黑色区域是一个轴对称图形并且对称轴平行于x轴,求最大黑色区域面积
首先取得答案时的对称轴纵坐标要么是整数要么是\(x.5\) ,枚举对称轴,维护两个集合,一个代表当前枚举的对称轴在矩形下半部分,一个表示上半部分,每次对称轴往上移动0.5,第一个集合里每一个元素都会给答案贡献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 #include <bits/stdc++.h> using namespace std;const int N = 3e5 + 10 ;int n, L[N], R[N], md[N], m;long long tmp, ans;int b[N * 3 ];int in[N * 3 ], change[N * 3 ], out[N * 3 ];int main () { scanf ("%d" , &n); for (int i = 1 ; i <= n; ++i) { scanf ("%d%d" , &L[i], &R[i]); L[i] = 2 * L[i] - 1 ; R[i] = 2 * R[i] - 1 ; md[i] = (0LL + L[i] + R[i]) / 2 ; b[3 * i - 2 ] = L[i]; b[3 * i - 1 ] = R[i]; b[3 * i] = md[i]; } tmp = ans = 0 ; sort (b + 1 , b + 3 * n + 1 ); m = unique (b + 1 , b + 3 * n + 1 ) - b - 1 ; for (int i = 1 ; i <= n; ++i) { in[lower_bound (b + 1 , b + m + 1 , L[i]) - b]++; change[lower_bound (b + 1 , b + m + 1 , md[i]) - b]++; out[lower_bound (b + 1 , b + m + 1 , R[i]) - b]++; } int down = 0 , up = 0 ; down += in[1 ]; for (int i = 2 ; i <= m; ++i) { tmp += 1LL * (down - up) * (b[i] - b[i - 1 ]); ans = max (ans, tmp); down += in[i]; down -= change[i]; up += change[i]; up -= out[i]; } printf ("%lld\n" , ans); return 0 ; }