Jason Fan.

XJ - NOI2021赛前训练题20 「2020~2021 年信息学多校联合训练 NOI2021 模拟赛」

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

92ce3867a25b048540c10275d83b5b1fe4f80d07b2eaafcdfcbf1cce59685bec981c6c4e63d59ce40dd35f6f2babe320547dc98990e526645e16a458562144600c26b6e5cf5464c87028d0e627431ac95754a54a8d17641dc1b1824b866ad906487016f97f7af951dd57cbb39733340fbf1f1e8015f6cbe6dfa3fe79fb3a8fb52ca394960aa7b45abdf8f1548005f962d5c0fbd311e9f7e584403344677a41bd43a789e25ca1e1f8d716fff37709ec7ae103a1fc76f054cfff1f8580024bf45128a01f93f65f51c2eb394f542f5c876cda66c65afa7458b8fbfd5eb2854f865c08d3ae162ed6700a32f5e258eacefec6df9e5310e6a0fd184 ...

92ce3867a25b048540c10275d83b5b1faff7d55fde65ccf7bbd5bff198b17deb2b728cc654dc85de9bb1c82617db721d66377a1b58f724bc35d460551dd2614e4d89bdbe42c9ffb79b60fd9b40bbd0cc5055fd2212cc8dc6f9b76f4f059a855cde6f6d3abd003c815e20db52c4eb21b78061bf71cc087138318f5482ff7b97f2e1f9c268177f6a5ba48208184b90641f61d2a87293f282112b4e979bab474ab9037bff28ba5bab9a76582d90e3340f2405849a2cadc0867f6a6aa6c323dfa7bf804cf2e4e05ea69e443bb618e17d19987669a708e4422c7ead5c8b71206847654b525c32f81df13c03700b68a3eec9d8a5b674c49ba9367da ...

92ce3867a25b048540c10275d83b5b1fe4f80d07b2eaafcdfcbf1cce59685bec981c6c4e63d59ce40dd35f6f2babe320cab95f45733f53cbf2ad908c9a29d3a458bacb5718db279db6cb666dab478974d6e1c9d7b4a4ba65606b8c9d6d8be69a2279432cf2d85e09228c0d925471ac5c3617bf2346336bfb4d3d22915308db294d5a1d24b42251324c5c825184dc563b5872045329b0308dc93d2cf7fa8d21ac31c27c45bd7212a69a6ab564d4506b7a537fa1ecff08d797a8f876ff1339c5eaba3f72b62a1093a0d4de42ca0f0791e17737fe0a66de8151b58c470b80b624df127d3b594909002a0742e96fede50c7d1c8a536dad7095f55 ...

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 ...

92ce3867a25b048540c10275d83b5b1fe4f80d07b2eaafcdfcbf1cce59685bec981c6c4e63d59ce40dd35f6f2babe320806ab462f552161cb16fc0c9bdf0bcba4600ded0840694b86bf593d22735972b4a76b4c074503388b9eba41b9ad4fa62515dff079a9fb04c8dc9f3d4e370c0b21f1d2b51dae5f7993f1199a172950d035a024a0039bb3eb579be55a92b4ae0f13e87dc4a18b1f0490dab2e20651da5b397c4681206088db4921b8621c562d4f53643d9dcf8c767498221e408412488fc61dd5c7f083596065960875beb1e9cd41c456d1db8f2dcc12aa5bd1a557e9728e5a3d36db1bebebb6eecfca14c0cd20384cbb0f19810f1e68 ...

题意 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 ...