Jason Fan.

XJ - NOI2021赛前训练题19 「第 1 届长沙市一中全国赛模拟赛 HNFMS NOI 2021」

fdbc2997623a61cf73a7235ddd759531c5c1d64aa56d5f2b54a26e0ff5aca404691e5fc60ba7c499cfa1158c115698c384c5c999668372575c504f80acd1ea133783bb58bc51d07ee8984dbb9bf9df03562fd4c4d1e057e3396704ba04a19e980b0b39db1005adf6c3b418276f8acc650afec3b503cfd1bcc336579c319eee6c316695e98b70dde9562b51521a6b4544a4a79d7fd09b407391a634fdfafab85829d616fbad617b0c8d05b030c89b7b755b3ac4f6503e03546ffe5471bf8042614848169de2f13ac07aad8dbe45695e27da5d4dfe3199e513d6b91ed53c5a77d0bf6dda680dc2a914dbb2002f1421e34412a0fa5e78c30ec41 ...

fdbc2997623a61cf73a7235ddd7595317a2ccbb3a6c7b9c72acd69409a28908ac18049a3ea5f5ce56d40603c7e549729690e7e1e547db20018b18ae9a0721b95a4f2d4e962a74d6b275f85837d27116191ffcbcab6fe4cf2f6f6b009d4415fdec19cdbe36ab6864fb622be4d747b119e94b39eba44d4ef0f5cb32e473f666d65a6111e844097d023967a2948fe9ba844c8f2616498582e5a6cf201bc6a2d7ea4a6c1e9d83bc92aee662f94e3ed31d2bdb6aeb2b0d456cfdd12bea526b064a2967e321a46c58c37a9bdf3487b4d227adf75e1e2ca128c3612ebd3921d64d63bafbf2a4483ad89bdf91ebb94283491cb4115e425f3780a128fc ...

fdbc2997623a61cf73a7235ddd759531c5c1d64aa56d5f2b54a26e0ff5aca404691e5fc60ba7c499cfa1158c115698c3c8de818ad1c5b49c4d91c657af3976e6ed75bb9ad1b94ddc3defe4ea2f4de8ba6bf9ec1650da60e173b354afbb9cd933d98522ef3dd52cd8ea9c978e7c6805194830ef2c2dd09b52493336f12745be8ba2896d230a5dfd524e0313eed13adc7a0bb2fb9121b69aa93716b7741d7a73a2c95f6b24935920de14070092530f7ec124dfc5f3984e20e9005059a33c71109907002dc8b6981491ed3240bd3ecc7be403636f3872fcaf95c25aeaf14fe4d95641b758bca06267de90affb1b2bf70e6e961576fe92b61d81c ...

CF1205E 题意 定义 f(s)f(s)f(s) 表示字符串 sss 的 border 的个数。 求字符集大小为 kkk，长度为 nnn 的字符串 f(s)2f(s)^2f(s)2 的期望。 题解 g(s,i)g(s,i)g(s,i) 表示 s[1:i]s[1:i]s[1:i] 是否为 sss 的 border。重要性质： border   ⟺  \iff⟺ 周期。 f(s)2=∑i=1n∑j=1n[g(s,i)∧g(s,j)]f(s)^2=\sum_{i=1}^{n}\sum_{j=1}^n [g(s,i)\wedge g(s,j)] f(s)2=i=1∑n​j=1∑n​[g(s,i)∧g(s,j)] E=1kn∑s∑i=1n−1∑j=1n−1[g(s,i)∧g(s,j)]=1kn∑s∑i=1n−1[g(s,i)]∑j=1n−1[g(s,j)]=1kn∑i=1n−1∑j=1n−1∑s[ s 有 i 周期，j 周期 ]=1kn∑i=1n−1∑j=1n−1∑s[ gcd⁡(i,j) 是 s 的周期 ]\begin{aligned} \mathbb{E}=&\frac{1}{k ...

fdbc2997623a61cf73a7235ddd759531c5c1d64aa56d5f2b54a26e0ff5aca404691e5fc60ba7c499cfa1158c115698c31e0c88deda781ee42e6e81411fefc21d2252b92996b40edba252da041314148ba99270087b4667d394ba46a8a55ef71d60cec7659f1bfedd611bfb4abd904d443f8006be72d7f4a773b1f374b36ee72284e0d2afc5fa8a4e47acaffb423024307d059e102dfda5a9922d3477b588a28cbe8ff8a55eca7b25ccb52a68017dd43f5030fc024eba7b4c061f0cc3b04c4afeb67985761f44a2c633117bcb30ae686c94509aa6b344ad9eb0aec0ac72f0df5fae01668b89744953250ad8c71e223c9ecf6bdb1878b8844cc ...

题意 luogu - P4619 [SDOI2018]旧试题 ∑i=1A∑j=1B∑k=1Cσ0(ijk)\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C \sigma_0(ijk) i=1∑A​j=1∑B​k=1∑C​σ0​(ijk) σ0(x)\sigma_0(x)σ0​(x) 表 xxx 约数个数。 多测 T≤10T\le 10T≤10，1≤∑max⁡(A,B,C)≤2×2×1051\le \sum \max(A,B,C)\le 2\times 2\times 10^51≤∑max(A,B,C)≤2×2×105。 题解 下文简记 gcd⁡(i,j)=(i,j)\gcd(i,j)=(i,j)gcd(i,j)=(i,j)，lcm⁡(i,j)=[i,j]\operatorname{lcm}(i,j)=[i,j]lcm(i,j)=[i,j] 显然有结论，就当作 σ0\sigma_0σ0​ 的性质吧。 σ0(ijk)=∑x∣i∑y∣j∑z∣k[(x,y)=1][(x,y)=1][(y,z)=1]\sigma_0(ijk)=\sum_{x|i}\sum_{y|j}\ ...

基础莫反，推式子。 「SPOJ 5971」LCMSUM SPOJ LCMSUM TTT 组数据，每次求： ∑i=1nlcm⁡(i,n)\sum_{i=1}^n \operatorname{lcm}(i,n) i=1∑n​lcm(i,n) T≤105,n≤106T\le 10^5,n\le 10^6 T≤105,n≤106 ∑i=1nlcm⁡(i,n)=∑i=1ni×ngcd⁡(i,n)=12(∑i=1n−1i×ngcd⁡(i,n)+∑i=n−11i×ngcd⁡(i,n))+n=12(∑i=1n−1i×ngcd⁡(i,n)+∑i=n−11i×ngcd⁡(n−i,n))+n=12∑i=1nn2gcd⁡(i,n)+n2\begin{aligned} &\sum_{i=1}^n \operatorname{lcm}(i,n)\\ =&\sum_{i=1}^n \frac{i\times n}{\gcd(i,n)}\\ =&\frac{1}{2}\left( \sum_{i=1}^{n-1} \frac{i\times n}{\gcd(i,n)} +\sum_{i=n- ...

泰勒展开，LCT 题解 题目都告诉你了： 若函数 f(x)f(x)f(x) 的 nnn 阶导数在 [a,b][a,b][a,b] 区间内连续，则对 f(x)f(x)f(x) 在 x0 (x0∈[a,b])x_0 \ (x_0\in[a,b])x0​ (x0​∈[a,b]) 处使用 nnn 次拉格朗日中值定理可以得到带拉格朗日余项的泰勒展开式 f(x)=∑k=0n−1f(k)(x0)(x−x0)kk!+f(n)(ξ)(x−x0)nn!,x∈[a,b]f(x)=\sum_{k=0}^{n-1}\frac{f^{(k)}(x_0)(x-x_0)^k}{k!}+\frac{f^{(n)}(\xi)(x-x_0)^n}{n!},x\in[a,b] f(x)=k=0∑n−1​k!f(k)(x0​)(x−x0​)k​+n!f(n)(ξ)(x−x0​)n​,x∈[a,b] 其中，当 x>x0x > x_0x>x0​ 时，ξ∈[x0,x]\xi\in[x_0,x]ξ∈[x0​,x]。当 x<x0x < x_0x<x0​ 时，ξ∈[x,x0]\xi\in[x,x_0 ...

概述 Hash （散列函数），其核心思想在于，将输入映射到一个值域较小、可以方便比较的范围。这种转换是一种压缩映射，也就是说，不同的输入可能会映射到相同的值，造成哈希碰撞。 在 OI 中我们常用哈希来比较两数据是否相同，如：字符串哈希（序列哈希），树哈希（树同构），集合哈希。还有一种以 「key-value」 形式存储数据的数据结构：哈希表。 我们通常会设计一个 Hash 函数 FFF 将不方便比较的数据映射到整数。我们希望通过这个函数判断两个数据是否相等，具体来说，哈希函数最重要的性质可以概括为下面两条： 在 Hash 函数值不一样的时候，两个数据一定不一样； 在 Hash 函数值一样的时候，两个数据不一定一样（但有大概率一样，且我们当然希望它们总是一样的）。 字符串哈希（序列哈希） 顾名思义，就是用哈希来判断字符串（序列）是否相等。 实现 通常我们采用的是多项式 Hash 的方法，现有 一个长度为 nnn 的字符串 SSS（下标以 111 开始），我们定义哈希函数 （其中 b,Mb,Mb,M 都是常数） F(S)=∑i=1nS[i]×bn−i(modM)F(S)=\sum_{i ...