交互
CF2210E CF2210E. Binary Strings are Simple? 交互。 猜测长度为 NNN 的 01 串。 每次询问子串 S[l…r]S[l\dots r]S[l…r]，返回子串所有循环移位的逆序对数 mod 子串长度的集合大小。 询问的代价为 Nr−l+1\dfrac{N}{r-l+1}r−l+1N，总询问代价不超过 max(30,3N)\max(30,3 N)max(30,3N)。 最多可以猜测 222 次。 当循环左移 1 时贡献是 −c0=c1−n-c_0=c_1-n−c0=c1−n，否则是 c1c_1c1，逆序对在模意义下的增量总是 c1c_1c1。因此询问实际是 #{x:x=kc1 mod N,k∈[1,N]}=Ngcd(N,c1)\#\{x : x=kc_1\bmod N, k\in[1,N]\} = \displaystyle\frac{N}{\gcd(N,c_1)}#{x:x=kc1modN,k∈[1,N]}=gcd(N,c1)N。 奇偶。在仅知道...
2025 ICPC 沈阳 C
2025 ICPC 沈阳 C 【题意】第一次运行给定 NNN 个正整数 Xi∈[1,M]X_{i} \in [1,M]Xi∈[1,M]，为每个数构造一个长度为 3M3 M3M 的序列，每个序列中 111 到 MMM 的整数恰好出现 3 次。jury 独立地将每个序列映射成二进制序列，第二次运行需要从这些二进制序列中解密出每个 XiX_{i}Xi。 很牛的题。喜欢 communication。 【思路】既然是 3M3M3M 且恰好出现 3 次，我们就分成三段，每段是长为 MMM 的 permutation。第一段就设为 1,2,…,M1,2,\dots,M1,2,…,M，这样直接知道每个字符映射成 0 还是 1 了。然后想想后面两个 permutation 怎么搞才能保证是单射。 最简单的方法是 rotation（循环移位），直接移 XiX_{i}Xi 位。 可以吗？有个小问题，如果映射出的序列有周期 TTT，那就分不出来了。比如原串是 1010，移位后是 0101，移了 1 还是 3 不得而知。 如何修正？什么串没有周期？素数！给...
FWT
123456789101112131415161718192021222324252627282930313233#include <vector>#include <utility> // for std::swaptemplate <typename T>void FWT(std::vector<T>& f, T m00, T m01, T m10, T m11) { const int N = f.size(); for (int k = 1; k < N; k <<= 1) { for (int j = 0; j < N; j += (k << 1)) { for (int i = 0; i < k; i++) { T& u = f[i + j]; T& v = f[i + j + k]; ...
多组数据
给定长度为 NNN 的序列 A=[A1,A2,…,AN]A = [A_1, A_2, \dots, A_N]A=[A1,A2,…,AN]。 定义其一个 有效分拆 为将其切分为 kkk 个相邻的子数组，各段长度依次为 L1,L2,…,LkL_1, L_2, \dots, L_kL1,L2,…,Lk（满足 Li≥1L_i \ge 1Li≥1 且 ∑i=1kLi=N\sum_{i=1}^k L_i = N∑i=1kLi=N）。 令第 iii 个子数组的起始下标为 Si=1+∑j=1i−1LjS_i = 1 + \sum_{j=1}^{i-1} L_jSi=1+∑j=1i−1Lj。 序列 AAA 被认为是合法的，当且仅当存在一种分拆同时满足以下两种条件： 条件 1（Type 1）： 对于所有子数组，其首元素等于该段长度减一。 ∀i∈[1,k],ASi=Li−1\forall i \in [1, k], \quad A_{S_i} = L_i - 1 ∀i∈[1,k],ASi=Li−1 条件 2（Type 2）： 第一段长度为 111...
Non-overlapping Subsegments
Problem - E - Codeforces Arseniy decided to make his friends Dabir and Egor happy. For this, he decided to give each of them an array of numbers of the same length. An array bbb is called good if its elements can be rearranged so that for all i>1i \gt 1i>1 the condition bi−bi−1=1b_i - b_{i - 1} = 1bi−bi−1=1 holds. Arseniy wants Dabir and Egor to be able to play with these arrays. For this, the following conditions must be satisfied: Each of the given arrays is good. If you write one...
Fast Exponentiation
快速幂 Fast Exponentiation 1234567891011// Quick powertemplate<class T>constexpr T qpow(T a, u64 n) { T res = identity(a); for (; n; n /= 2, a *= a) { if (n & 1) { res *= a; } } return res;} 矩阵快速幂 1234567891011121314151617181920212223242526272829// ---------------- Matrix ---------------- //using Matrix = std::array<std::array<Z, 64>, 64>; // change here for different size or typeconstexpr Matrix...
背包
ABC436G - Linear Inequation 求 ∑i=1NAixi≤M\displaystyle\sum_{i=1}^N A_i x_i \le Mi=1∑NAixi≤M 的非负整数解数量。N≤100N\le100N≤100，Ai≤100A _ i\le100Ai≤100，M≤1018M\le10 ^ {18}M≤1018。 完全背包是多重背包的特化，即每种物品充分多的多重背包。多重背包有经典的二进制优化。具体而言，每个物品 iii 拆分为 logM\log MlogM 个，重量分别为 2mAi2^m A_i2mAi。如此，问题化为 01 背包。 考虑背包压缩：如果我们将 20Ai2^0 A_i20Ai 的物品全部统计了，那么以后将不会有重量为奇数的物品。因此，剩余容量 2k,2k+12k,2k+12k,2k+1 的方案可以合并至 kkk，然后令 MMM 减半。 12345678910111213141516171819const int V = std::ranges::fold_left(A, 0LL,...
未命名
ABC434F - Concat (2nd) NNN strings SiS_iSi. Find the second lexicographically smallest string when concatenating SiS_iSi in any order. Let S1′,S2′,…,SN′S'_1,S'_2,\dots,S'_NS1′,S2′,…,SN′ be the result of sorting in the order defined by X<YX<YX<Y iff XY<YXXY<YXXY<YX. If N=2N=2N=2, then the answer is S2′S1′S'_2S'_1S2′S1′. If there exists an integer 1≤i<N1 \le i < N1≤i<N such that Si′Si+1′=Si+1′Si′S'_i...
连续段插入型 DP
【P5999】求排列 ppp 的数量，满足 pip_ipi 两边的数同时小于或大于 pip_ipi，且 p1=Sp_1=Sp1=S, pN=Tp_N=TpN=T。 f(n,m)f(n,m)f(n,m)：前 nnn 小的值分成 mmm 段的方案数。 从小到大加入每一个数，考虑现在枚举到 nnn，若 n≠Sn \neq Sn=S 且 n≠Tn\neq Tn=T，则可以分三种情况讨论： 新开一段 若 n≠Sn \neq Sn=S 且 n≠Tn\neq Tn=T，以后 nnn 两侧的都比它大，与题意相符，转移 f(n,m)←(m−[n>S]−[n>T])f(n−1,m−1)f(n,m) \gets (m-[n>S]-[n>T]) f(n-1,m-1)f(n,m)←(m−[n>S]−[n>T])f(n−1,m−1)。 若 n=Sn = Sn=S 或 n=Tn = Tn=T，与题意相符，转移 f(n,m)←f(n−1,m−1)f(n,m) \gets f(n-1,m-1)f(n,m)←f(n−1,m−1)。 接在某一段头...