Jason Fan.

「牛客」货物分组 题意简述 nnn 个物品，第 iii 个物品重量为 aia_iai​ ，要求按顺序连续放入若干箱子，每个箱子物品总重不超过 WWW ，箱子从 111 开始按序编号，对于第 iii 个箱子 ，其代价为 i×(箱中货物总重)+(箱中最大货物重量)−(箱中最小货物重量)i \times \text{(箱中货物总重)}+\text{(箱中最大货物重量)}-\text{(箱中最小货物重量)} i×(箱中货物总重)+(箱中最大货物重量)−(箱中最小货物重量) 求最小总代价 注：数据范围 对于 10%10\%10% 的数据，n≤10n\leq 10n≤10 对于 30%30\%30% 的数据，n≤500n\leq 500n≤500 对于 60%60\%60% 的数据，n≤5000n\leq 5000n≤5000 对于 100%100\%100% 的数据，n≤105,1≤ai≤W≤105n\leq 10^5,1\leq a_i\leq W\leq 10^5n≤105,1≤ai​≤W≤105 题解 30pts 先记 sn=∑i=1nais_n=\sum_{i=1}^{n} a_isn ...

fdbc2997623a61cf73a7235ddd7595318b33e643f3cb00c209b6165956d742b3407e70791ad19f62e09e090f30f5c98cdeffe1e2aeeb487afd2d63c1772cd1cb55bc74575da0df38c4885be62b498e53e181d48d47fc231f65c4c2da6aa9dd59b42104ebe99df5053b8862ed1923f1ae739a1ceec488ecd702b1ad4e119080637552d766cc125660604dcdcfa0017e2ec0b661e6d26b6f117eedf6f847cb38f2fb9b42ca6f58ae4d1d8faa8b50666fcb8a990626414123933023ae2a95ff3f4fc0105ede4a4b84abde3936733aa39480086a5ca63816d76d74a159be2199d0bc0e401b4ae26682005fa85ea7f805e731873ec38aaa15d161a ...

fdbc2997623a61cf73a7235ddd759531c5c1d64aa56d5f2b54a26e0ff5aca40435936bfac755d0e80d47276d76b38467db187d9f41d82e4259ca7d04ad57f76c602f9c4c719c6cfbc54594a2aeba3263118c3b23019774cf6fe7b3bf12284276847ec070b44ffeda0831c15def619391f3eceb475fe8b9a2bced4e91375006df73aa88f48e77025ebc97cce18069576505de5e0598275197da6a30f55f45b6024d1c97078968fa02e40933d502ec5aa03c72a60b20c11c1fbe1510bcc90b5895684505c4da35a80aba6cfc2e24f0af83e5d134dce19b662add8a7727f43a578d9ef67cb0c929ec77e8e2ae5f1dd7ee963b0b2f080e04bdb49 ...

fdbc2997623a61cf73a7235ddd759531c5c1d64aa56d5f2b54a26e0ff5aca404691e5fc60ba7c499cfa1158c115698c3d410f96f21ae16174dd74a7569cb12a5d7526012d170d7dc076ce65b083ff22dca84c8a428e5f3520ae6d066154357db4daf1bf2032a3f2af346e47e5d7bf46441d90c1bef2ddef5232254b9334a0b35209457ccd48d65a44fdefd3ce3f201874f8160b0c0ced25cb24bfab30bb1ce8ec9f3b2061c1bd5049ecffbfc8676470237bdd6911ae91f28e7567388cec900ab79f99f883b1212d11b028627790f3460ee7782504369ddd8dec1531408539ed5590789a54c15e3baaf991c2eb52cb0db30cea96047a4d7ab1 ...

fdbc2997623a61cf73a7235ddd759531c5c1d64aa56d5f2b54a26e0ff5aca40435936bfac755d0e80d47276d76b38467db187d9f41d82e4259ca7d04ad57f76c602f9c4c719c6cfbc54594a2aeba3263118c3b23019774cf6fe7b3bf12284276887d005ea1b902ba5cc72ffa89c0de0f90c322cf008ff5ce2caa8e2582a477c6c17d50967110f50190bb63c840f7d259a3f0bb21566d2fa11f58e138de0d3499d62d0bc1f3b1cb51db649b587ae24829cddcea7e4082da0a49d576bf59776fad7173626908136310eb4dccd6ba6d2d4090db3f55eb400fd4434c4063500788f635960fe7e0cf6f8dff7eb94025da286b75b4fb4757d8f59f4 ...

多少个1？ BSGS，数论 一句话题意： 满足 111…11⏟n≡K(modm)\underbrace{111\dots11}_n \equiv K \pmod{m}n111…11​​≡K(modm) ，给你 K,mK,mK,m ，求符合条件 nnn 的最小值。 30%30 \%30% 的数据保证 m≤106m\leq 10^6m≤106。 60%60 \%60% 的数据保证 m≤5×107m\leq 5\times 10^7m≤5×107。 100%100 \%100% 的数据保证 m≤1011  ,  0<K<mm\leq 10^{11}\;,\;0<K<mm≤1011,0<K<m 。 60pts 这档分应该很好拿，原式可以拆成这样： 100+101+102+⋯+10n−1≡K(modm)10^0+10^1+10^2+\cdots +10^{n-1} \equiv K \pmod{m} 100+101+102+⋯+10n−1≡K(modm) 又因 10⊥m10 \perp m10⊥m ，10x mod m10^x \bmod m10xmodm ...

[SDOI2010]古代猪文 简述一下题意就是让你求 g∑k∣n(nk) mod 999911659g^{\sum_{k\mid n} \binom{n}{k} } \bmod 999911659 g∑k∣n​(kn​)mod999911659 如果 g=999911659g=999911659g=999911659 显然答案等于 000 ，否则根据欧拉定理上式等价于： g∑k∣n(nk) mod 999911658 mod 999911659g^{\sum_{k\mid n} \binom{n}{k} \bmod999911658} \bmod 999911659 \\ g∑k∣n​(kn​)mod999911658mod999911659 注：φ(999911659)=999911658\varphi(999911659)=999911658φ(999911659)=999911658 。 然后发现 999911658999911658999911658 不是素数，有些数不存在对其的逆元，而且这个模数太大，Lucas会TLE 。怎么办？ 可以发现 999911658=2×3×4 ...

名为扩展中国剩余定理，但解法与CRT没啥关系 关于CRT 简介 考虑求解如下线性同余方程组，不保证 ∀i,j,  mi⊥mj\forall i,j,\;m_i\perp m_j∀i,j,mi​⊥mj​ {  x≡a1(modm1)x≡a2(modm2)x≡a3(modm3)⋮x≡an(modmn)\left\{\; \begin{matrix} x & \equiv & a_1 & \pmod{m_1} \\ x & \equiv & a_2 & \pmod{m_2} \\ x & \equiv & a_3 & \pmod{m_3} \\ & \vdots & & \\ x & \equiv & a_n & \pmod{m_n} \\ \end{matrix} \right. ⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​xxxx​≡≡≡⋮≡​a1​a2​a3​an​​(modm1​)(modm2​)(modm3​)(modmn​)​ CRT在处理线性同余方程组时 ...

📘数论知识，高次同余方程求解，形如：ax=n(modp)a^x=n\pmod{p}ax=n(modp) 。BSGS （Baby Steps Giant Steps）又名大步小步算法，又名北上广深 。 前置知识 逆元：数论基础 - 乘法逆元 哈希表 或 map BSGS 对于如下的同余式，且满足 a⊥pa\perp pa⊥p ，求 xxx ax≡n(modp)a^x\equiv n\pmod{p} ax≡n(modp) 解法 首先一个显然的结论 x∈[0,p−1]x\in[0,p-1]x∈[0,p−1] ，根据欧拉定理 aφ(p)≡1(modp)a^{\varphi(p)}\equiv 1\pmod{p}aφ(p)≡1(modp) ，且 φ(p)<p\varphi(p)<pφ(p)<p，xxx 大于 p−1p-1p−1 后 axa^xax 的取值肯定在之前就出现过，要得到最小的解只要考虑 x∈[0,p−1]x\in[0,p-1]x∈[0,p−1] 即可。 令 x=A×⌈p⌉−B  ∣  A,B∈Nx=A\times\lceil \sqrt{p}\rceil-B\; ...

「USACO18JAN」 Stamp Painting G 动态规划，dp优化 题面 题目描述 Bessie has found herself in possession of an NNN-unit long strip of canvas (1≤N≤1061 \leq N \leq 10^61≤N≤106) and she intends to paint it. However, she has been unable to acquire paint brushes. In their place she has MMM rubber stamps of different colors (1≤M≤1061 \leq M \leq 10^61≤M≤106), each stamp KKK units wide (1≤K≤1061 \leq K \leq 10^61≤K≤106). Astounded by the possibilities that lie before her, she wishes to know exactly how many different ...