Jason Fan.

「牛客」排列计数机 题意 定义一个长为 kkk 的序列 A1,A2,…,AkA_1,A_2,\dots,A_kA1​,A2​,…,Ak​ 的权值为：对于所有 1≤i≤k1\le i\le k1≤i≤k，max⁡(A1,A2,…,Ai)\max(A_1,A_2,\dots,A_i)max(A1​,A2​,…,Ai​) 有多少种不同的取值。 给出一个 111 到 nnn 的排列 B1,B2,…,BnB_1,B_2,\dots,B_nB1​,B2​,…,Bn​，求 BBB 的所有非空子序列的权值的 mmm 次方之和。 答案对 109+710^9+7109+7 取模。 数据范围: 1≤n≤105,1≤m≤20,1\le n \le 10^5 ,1\le m \le 20,1≤n≤105,1≤m≤20, 保证 BBB 是 111 到 nnn 的排列。 题解 这种序列上的问题多是DP。 暴力DP 首先先考虑一个比较暴力的DP fv,jf_{v,j}fv,j​ 表示最大值为 vvv ，序列的权值为 jjj 的方案数。按顺序枚举 iii ： fAi,j=∑k∈[1,Ai−1]fk,j−1,j∈[2 ...

「牛客」货物分组 题意简述 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 ...

92ce3867a25b048540c10275d83b5b1fcf3027232b13c26c1a635d49d722095be6203a4b3a5630a17403c4704cf2cc85e3b02d274d434e0524c3ead1de1f5cb51f094011c3c45062cbac64519c3596d604341f5c869425a2f34b32fbf027dbd000f6e6668181554510c9f06eddcf85bbda3400c89664e94546fa905c40482fab03b5bc2c08586d51cf1be7fe2361d5943156df471c2eb00e7291b2bf75aef5b738b4de0ec5a1bf6f3c5060acb14b078c37ddf1fb88346ddb4d98c6b05a5fe053a8a9f97f2b5748412a684122e564162d3c2b6f6566e2f8715c86ac79f9820b8cd89311ae713affc206cda7677125e49dd2bcbd48157730a6e ...

92ce3867a25b048540c10275d83b5b1fe4f80d07b2eaafcdfcbf1cce59685beccc932a92d7c1af1ffe6333b2335c25c2b30f39e12e50be0efedeff672989bf593f109ae098125046c3c2e87980f9c8bdd3157bc3d276981666b0ad5da08f911d4d893adddfcc82a402a3c741d6ff63fad203c5f2acfe4c572da3848ed7737e5eb64cd8fd02b807dafef23926d93556cb5ee5673d6b4acd417c23299247f2edd268afeca58f73d8a5290749b1d9c3dd8f2a0f9d2ff573c332e23615c866f2d452a780505bf5a3b2b77b9ef7415fdbf0608aa81ae585b83d1286e599ea3f87c2a5fae92920898055d6f190f6ae7d07a946965ee53c2bef571e5 ...

92ce3867a25b048540c10275d83b5b1fe4f80d07b2eaafcdfcbf1cce59685bec981c6c4e63d59ce40dd35f6f2babe3204fa2c26c90b80dbf0cf831128b4960b8f7f6f08f38623e5e6c249dc7c0d0d38c4cda9a9fecd698aff83409396f41552b0320f7a2b3c0bcf48b2e1bddb1ffb3895d231dcf8c2e9f4a2f8b824a514708f69f076dda0ff2a240e9e0fdbc5e9613678c92e24e61164c015af6fcbcbdc612f1f34af2643009f8e2e84cf7ef12796f0634799dce53e23671e12578c59012ad9d5da1e8273a14e07d2dda9775c4f05d6d7db6b21d3d949043295ed86cf159a017e72e20c9e996774cc96bbcfa15f150d618de575e0ce6ac794 ...

92ce3867a25b048540c10275d83b5b1fe4f80d07b2eaafcdfcbf1cce59685beccc932a92d7c1af1ffe6333b2335c25c2b30f39e12e50be0efedeff672989bf593f109ae098125046c3c2e87980f9c8bdd3157bc3d276981666b0ad5da08f911dd417c1e74e229abea95bd17b06ec392baed71ee0d1ddb371e9b880a241561ad9b8cdaf352199edb96ef3198fa71df90bd3b8075f323ab424d16b2db937be46f81bdf59472ffb53fe05886e6d2bc60250d58bfd3d270ccc8b2666ce62a090d58d8726af756a9b11b9a9c1a2aa8c14c1f1184b6236ab18191a337a5723e5eefc387d0edb794b9abcd40f60772a056f39b7def8b4ddfa7ffd700 ...

多少个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\; ...