参考博客exLucas：求\(C_n^m\bmodd\)(\(d\)不一定为质数)1.将\(d\)质因数分解为\(d=p_1^{c_1}\timesp_2^{c_2}\times\cdots\timesp_k^{c_k}\)\(\foralli,j\in[1,k]\),\(p_i^{c_i}\)与\(p_j^{c_j}\)互质，所以可以构造出如下同余方程：\[\begin{cases}a_1\equivC_

题意给定一个长度为\(n\)的序列\(\{a_1,a_2,\dots,a_n\}\)。现在要在\(a\)选出非空子序列\(\{b_1,b_2,\dots,b_m\}\)，使得所有的\(i\in[1,m]\)，都有\(b_i\bmodi=0\)。求能够选取\(b\)序列的方案数模\(10^9+7\)的值。思路定义\(dp_{i,j}\)表示在\(\{a_1,a

思路定义\(dp_{i,j}\)表示将前\(i\)个数，正好分为\(j\)组的方案数。那么，我们对\(i\)号元素进行分类讨论：将\(i\)放入原本就存在的组中，因为在同一个组中不能存在两个数\(x,y\)，使得\(x\bmodm=y\bmodm\)。所以对于\(i\)，如果它是\(m\)的倍数，则在\(1\simi-

记录一下，下文的除法非特殊注明都是向下取整。求\(F(n,k)=\sum_{i=0}^{k}\binom{n}{i}\pmodp\)。首先使用卢卡斯定理。\[\begin{aligned}&\sum_{i=0}^{k}\binom{n}{i}\\=&\sum_{i=0}^{k}\binom{\frac{n}{p}}{\frac{i}{p}}\binom{n\bmodp}{i\bmodp}\\=&\s

乘法逆元若\(a\timesb\equiv1(\bmod\c)\)，且\(\gcd(a,b)=1\)，那么我们定义\(a\)为\(b\)的逆元，也可以称\(a\)是\(b\)在\(\bmod\c\)意义下的倒数。费马小定理对于质数\(p\)和任意整数\(a\)，有\(a^p\equiva(\bmod\p)\)。反之，若\(a^p\equiv

题目传送门简化题意给定\(H,n\)和一个长度为\(n\)的序列\(d\)，求一个最小的\(m\)使得\(H+\sum\limits_{i=1}^{m}d_{(i-1)\bmodn+1}\le0\)。解法将式子移项后得到\(\sum\limits_{i=1}^{m}-d_{(i-1)\bmodn+1}\geH\)。将\(\sum\limits_{i=1}^{m}-d_{(i-1)\bmo

T1考虑只有第二种操作。显然可以维护\(a_i\)代表当前序列的第\(i\)个数是什么。观察到变换只和\(k\%3\)的值有关。对于第一种操作，显然可以令\(k\leftarrowk\%n\)。观察到这种变换将整个序列视为一个环更方便一点，于是维护变换后第一个数的下标是多少。输出时按照环的

A.DistanceMod5考虑一个点\(x\)向外的最短路树，如果两个点不满足\(dis_{i,x}=(dis_{j,x}+1)\bmod5\)或\(dis_{j,x}=(dis_{i,x}+1)\bmod5\)，那么这两个点一定没有连边，否则可能有连边。去除掉所有不可能的连边，剩下的连上边，发现这样是最优的。然后floydcheck

2024040前言离散数学是本书的重点，而整数又是离散数学的中心议题。数论是讨论整数性质的重要数学分支，因此我们要来探索它。​ ——《具体数学》第四章标有*的为拓展内容，或者说比较难的题目，但它们都非常有趣。部分题目的代

发现题目中描述的配对条件可以理解为：\(pc_i-pc_j=1\)且\(a_i\bmoda_j=0\)，其中\(pc_i\)表示\(a_i\)的质因数个数。自然想到以\(pc\)奇偶性建立二分图，可以配对的点间连一条边。先不考虑费用，三种边为：\((s,i,b_i)\)，其中\(pc_i\bmod2=1\)。\((i,t,b_i)\)，其中\(pc_i\bm

https://www.luogu.com.cn/problem/AT_abc354_dhttps://atcoder.jp/contests/abc354/tasks/abc354_d由图片可知，很显然每个\(4\times2\)​网格（称为单位网格）都是全等的。为了方便，将\(A,B,C,D\)都增加\(10^9\)，因为\(10^9\bmod4=10^9\bmod2=0\)，所以图形没有变化。（很重要，这

题目大意：\(f(x)=\begin{cases}x,1\lex\le9\\f(x的各数位之和),x>9\\\end{cases}\)求\(\sum_{i=1}^{n}f(i)\)。根据打表找规律，我们会发现\(f(x)=(x-1)\bmod9+1\)。所以\(\sum_{i=1}^{n}f(i)\)\(=\sum_{i=1}^{\lfloor\frac{n}{9}\rfloor\cdot9}f(x)+\sum_{i=\l

ABC207EModi显然有\(n^3\)的dp。设\(f_{i,j}\)表示前\(i\)个数里划分\(j\)段（\(i\)为第\(j\)段结尾）的方案数，\(s_i=\sum_{i=1}^ia_i\)，则有：\[f_{i,1}=1,f_{i,j}=\sum_{k=1}^{i-1}[s_i-s_k\equiv0\pmodj]f_{k,j-1}\]考虑进一步优化。我们发现上式可以化为：\[f_{

首先根据裴蜀定理，能走到的点\(x\)肯定满足\(\gcd(a,b)|x\)。于是令\(g=\gcd(a,b)\)，可以考虑求解\(\lfloor\frac{m}{g}\rfloor,\frac{a}{g},\frac{b}{g}\)，最后记得去判一下\([g\lfloor\frac{m}{g}\rfloor,m]\)这个区间，因为只有这个区间是不满（区间长度可能\(<g\)

书接上回...我们知道，我们在使用FFT时，靠的是单位根\(\omega\)。数学家证明这是复数域中唯一符合条件的数。可是它的浮点误差和带来的巨大运算时间使我们有点不能接受。于是，我们想想能不能找个替代品替代掉\(\omega\)。于是，原根就出现了！原根的引入阶对于一个数\(x\)，在

阶对于\(\gcd(a,p)=1\)，最小的\(t\)使得\(a^t\equiv1(\bmodp)\)称为\(a\)的阶。写作\(\operatorname{ord}_p(a)\)。若\(a^k\equiv1(\bmodp)\)，当且仅当\(\operatorname{ord}_p(a)|k\)。求阶的复杂度是\(O(\sqrt{n})\)。给定\(\gcd(a,p)=\gcd(b,p)=1\)，问是否存在

多项式乘法存在多项式\(F(z)=\sum_{i=0}^na_iz^i,G(z)=\sum_{i=0}^mb_iz^i\)，我们定义多项式乘法：\[F(z)*G(z)=\sum_i\sum_ja_ib_jz^{i+j}\]多项式的点值表达一个\(n\)次函数可以用平面上的\(n+1\)个点来表达。所以我们可以把一个\(n\)次多项式从系数表达转化成\(n+

！！！数论\(\sum_1^n[i\inprime]=O(\frac{n}{\logn})\)。算数基本定理是常识。经典问题：\(\gcd\times\operatorname{lcm}=a\timesb\)。埃氏筛\(O(n\log\logn)\)处理出\(1\simn\)的所有质数。对于所有质数扫描所有倍数。质数的倒数和为\(O(\log\logn)\)。P7960定义

数学能力太弱导致的.求\[[x^n]\frac{1}{\prod_{i=0}^m(1-(u+iv)x)}\]根据EI哥哥的博客\[\def\e{\mathrm{e}}[x^n]\frac{1}{\prod_{i=0}^m(1-(u+iv)x)}=\left[\frac{x^{n+m}}{(n+m)!}\right]\frac{\e^{ux}(\e^{vx}-1)^m}{v^mm!}=\frac{1}{v^mm!}\sum_{k=0}^

CodeforcesRound940(Div.2)andCodeCraft-23前四题难度适中，总体还算不错，我想想都能做。E题考察威尔逊和质数筛前缀和算贡献。F题是数据结构，据说很版，还没补。A题：题意：给出n个木棍，最多组成多少个多边形Solution：统计各长度木棍的数量，全部贪心成三角形voidsolve(){ cin>>n;

被数论虐爆了(悲)威尔逊定理\(\forallp\inprime,(p-1)!\equiv-1(\bmodp)\)为什么啊？对于\(2\)很显然。对于\(p\)，我们知道\(inv(p-1)=p-1=-1\)，然后\(inv(1)=1\)然后因为\(p\inprime\)，所以对于任意\(a\in[2,p-2]\)，都有\(inv(a)\)与它唯一对应。因为\(

由于首位不能是\(0\)，因此首位有\(b-1\)种可能性。其他\(n-1\)位有\(b^{n-1}\)种可能。因此这些数总计\((b-1)b^{n-1}\)每页\(c\)个数，求最后一页有多少个数，即求\(\text{ans}=(b-1)b^{n-1}\quad\bmodc\)注意到题目中\(b,n\)都非常大，采用扩展欧拉定理进行降

题意：解方程\[a^x\equivx\pmodm\]数据范围：\(a<m\le10^9\)Solution首先\(a^x\equiva^{x\bmod\varphi(m)+\varphi(m)}\pmodm\)我们设\(\text{solve}(\&x,y,m)\)表示解决\[a^{x\bmod\varphi(m)+y}\equivx\pmodm\]原题即\(\text{solve}(\&x,

Statement\(S(n,m)=\{k\midk\in\mathbbN^+\landn\bmodk+m\bmodk\gek\}\)，求\(\varphi(n)\varphi(m)\sum_{k\inS(n,m)}k\pmod{998244353}\)（\(n,m\le10^{15}\)）Solution欧拉函数怎么求就不说了，可以\(\mathcalO(\sqrtn)\)解决\(n\bmodk+m\bmodk

题面。翻译清晰，这里就不吐槽了。根据轮盘转动的方法，可以看出这是一个简单的高斯求和。因为这是一个轮盘，在轮盘中转动了\(now\)个格子与转动了\(now\bmodn\)所到达的格子是一样的（这就没必要证明了吧），因此我们很容易就能得到一个最朴素的代码： cin>>T; while(T--) { c