zcmimi's blog

arrow_back数论共123篇文章

avatar
zc
2020-10-16 21:05:56

查看原题

点击跳转

s_i为已经确定的m人中编号不小于i的个数

若存在s_i>n-i+1,显然无解

考虑动态规划,设f(i,j)表示剩下n-m个人中有j个人编号不小于i

\displaystyle f(i,j)=\sum_{k=0}^j f(i+1,j-k)\cdot {j\choose k}, 其中j\le n-s_i-i+1

最终答案为f(1,n-m)

avatar
zc
2020-10-14 18:06:50

查看原题

点击跳转

结论: \gcd(f_n,f_m)=f_{\gcd(n,m)},然后矩阵快速幂加速即可

证明:

m>n

引理:

  • \gcd(f_n,f_{n+1})=1

    根据辗转相减法, \gcd(f_n,f_{n+1})=\gcd(f_n,f_{n+1}-f_n)=\gcd(f_n,f_{n-1})

    所以 \gcd(f_n,f_{n+1})=\gcd(f_n,f_{n-1})=\dots=\gcd(f_2,f_1)=1

  • f_{n+m}=f_nf_{m-1}+f_{n+1}f_m

    数学归纳法:

    1. n=m=1时,成立
    2. 假设m,n\le k时成立,当n=k+1时:

      \begin{aligned} f_{n+m} &=f_{m+(k+1)}=f_{k+(m+1)}\\ &=f_mf_{k-1}+f_{m+1}f_k\\ &=f_mf_{k-2}+f_{m+1}f_k + f_{m+1}f_{k-1}+f_{m+2}f_k\\ &=f_{m+1}(f_{k}+f_{k-1})+f_{m}(f_{k-1}+f_{k-2})\\ &=f_kf_m+f_{k+1}f_{m+1} \end{aligned}

  • \gcd(f_{n+m},f_n)=\gcd(f_n,f_m)

    \begin{aligned} \gcd(f_{n+m},f_n) &=\gcd(f_nf_{m-1}+f_{n+1}f_m,f_n)\\ &=\gcd(f_{n+1}f_m,f_n)\\ &=\gcd(f_{n+1},f_n)\cdot\gcd(f_m,f_n)\\ &=\gcd(f_m,f_n) \end{aligned}

\begin{aligned} \gcd(f_n,f_m) &=\gcd(f_n,f_{m-n+n})\\ &=\gcd(f_n,f_{m-n}f_{n-1}+f_{m-n+1}f_n)\\ &=\gcd(f_n,f_{m-n}f_{n-1}) \end{aligned} \\ \because \gcd(f_{n},f_{n+1})=1\\ \therefore \gcd(f_n,f_{m-n}f_{n-1})=\gcd(f_n,f_{m-n})

这样一直碾转相减下去,就是f_{\gcd(n,m)}

avatar
zc
2020-09-28 20:30:29

查看原题

点击跳转

prufer序列应用模板

n个点的完全图有2^{n-2}棵生成树。

对于给定度数为d_{1\sim n}​的一棵无根树共有\dfrac{(n-2)!}{\prod_{i=1}^n(d_i-1)!}​种情况

全部全排列方案数除以每个点i的排列方案数(除去重复的)

i个点度数为d_i​,会在prufer序列中出现d_i-1次,全排列方案数为(d_i-1)!

由于答案很大10^17并且爆long long,过程中有除法,所以使用python3自带高精度非常方便

python3代码:

n=int(input())
if n==1: # 特判
    print(1 if int(input())==0 else 0),exit()
# 阶乘
f=[1]*(n+1)
for i in range(1,n+1):f[i]=f[i-1]*i
# 计算
ans=f[n-2]
tot=0
for i in input().split():
    x=int(i)
    if x==0:print(0),exit()
    ans//=f[x-1]
    tot+=x-1
print(ans if tot==n-2 else 0) # 特判

为了避免除法,我们可以换一种统计方式,

依次把第i个点d_i-1个出现的数插入到prufer序列中,答案乘以方案数,空位数减去d_i-1

记得特判

c++代码

avatar
zc
2020-09-28 11:26:35

查看原题

点击跳转

假设当前有了i个瓶盖,还差n-i个瓶盖

再买一个瓶盖在差的n-i个中的概率为\frac 1{n-i},

期望再买\dfrac n{n-i}次后拥有i+1个瓶盖

全部加起来就是\displaystyle \sum_{i=0}^{n-1} \frac n{n-i}

最终就是\displaystyle \left( \frac nn + \frac n{n-1}+\frac n{n-2}+\dots+\frac n1\right)

\frac xy+\frac ni=\frac {xi+yn}{yi}

avatar
zc
2020-09-27 21:04:47

查看原题

点击跳转

首先至少需要m-1个空位,然后剩下的n-m+1个位置可以乱放

答案: A_{n-m+1}^m

avatar
zc
2020-09-27 18:39:00

查看原题

点击跳转

题意:

\displaystyle \sum_{i\mod 2=0} {n\choose i}

题解

  1. {n\choose 0}+{n\choose 1}+{n\choose 2}+\dots+{n\choose n}=0
  2. {n\choose 0}-{n\choose 1}+{n\choose 2}-\dots+(-1)^n{n\choose n}=0
  3. {n\choose 0}+{n\choose 2}+{n\choose 4}+\dots={n\choose 1}+{n\choose 3}+{n\choose 5}+\dots=2^{n-1}

证明

二项式定理:

(a+b)^n={n\choose 0}a^n+{n\choose 1}a^{n-1}b+\dots+{n\choose i}a^{n-i}b^i+\dots+{n\choose n}b^n

a=b=1时,可证明1,

a=-1,b=1时,可证明2,

1式+2式可证明3

avatar
zc
2020-09-15 20:16:00
查看原题

点击跳转

g(n)为点数为n的无向图个数

g(n)=2^{n\choose 2}

f(n)为点数为n的简单无向连通图的数量

枚举连通块个数i可得

\displaystyle g(n)=\sum_{i=0}^n \frac{f(i)}{i!}

发现这个形式很眼熟(生成函数):

g=e^f

那么f=\ln g

求出g\ln就可以得到f

avatar
zc
2020-09-15 18:49:00
查看原题

点击跳转

给两个手环同时增加亮度,与给其中一个增/减亮度是一样的

同时旋转两个手环,旋转其中一个是一样的

设旋转后两个手环分别为a,b,其中一个加上x

那么就是让\sum_{i=1}^n (a_i-b_{i}+x)^2最小

\displaystyle \sum_{i=1}^n (a_i-b_{i}+x)^2\\ =\sum_{i=1}^n a_i^2+\sum_{i=1}^n b_i^2+nx^2+2x(\sum_{i=1}^n a_i-b_i)-2\sum_{i=1}^n a_ib_i

其中只有最后一项是变化的,前几项都可以直接求得

nx^2+2x(\sum_{i=1}^n a_i-b_i)是关于x的二次函数,直接求得最小值

考虑\sum_{i=1}^n a_ib_i

可以发现\sum_{i=1}^n a_{n-i+1}b_i是卷积的形式

那么我们把a倍长,把b翻转,然后再卷积,得到n+12n次项中的最大值就是\sum_{i=1}^n a_ib_i的最大值

avatar
zc
2020-09-14 16:15:00
查看原题

点击跳转

从大到小枚举n的因子x

如果能够满足那么x+2x+\dots+kx\le n

x(1+2+\dots+k)\le n\\ \dfrac{xk(1+k)}{2}\le n\\ xk(1+k)\le 2n

其中x\le \dfrac{2n}{k(1+k)}

找到最大的x后,按顺序输出x,2x,\dots+(k-1)x,最后一个数为n减去前面的数的和

avatar
zc
2020-09-11 22:22:00
查看原题

点击跳转

可以发现查询的c\le 20,那么我们直接对每个节点记录每个c的答案

区间加

设当前区间a_1,a_2,\dots,a_n

区间加后:a_1+x,a_2+x,\dots,a_n+x

选取i个方案:

\begin{aligned} &\quad (a_1+x)(a_2+x)\cdots(a_i+x)\\ &=a_1a_2\cdots a_i+xa_2a_3\cdots a_i+x^2a_3a_4\cdots a_i+\dots\\ &=a_1a_2\cdots a_i+\sum_{j=1}^ix^j \left( \text{从i个数中取出i-j个数的乘积之和} \right) \end{aligned}

该区间取i个数的乘积之和增加的贡献:

\displaystyle ans_i\operatorname{+=}\sum_{j=0}^i x^{i-j}ans_j{n-j\choose i-j}

区间反转

选取奇数个的答案变成相反数

选取偶数个的答案没有影响

区间查询

设当前答案为ans,左儿子答案为l,右儿子答案为r

\displaystyle ans_i=\sum_{j=0}^i l_j\times r_{i-j}

(左边选j个,右边选i-j个)

4/13
Search
search