# 算法竞赛

Acwing1307 牡牛和牝牛

原题链接:Acwing1307

题目描述:约翰要带 $N$ 只牛去参加集会里的展示活动,这些牛可以是牡牛,也可以是牝牛。

牛们要站成一排,但是牡牛是好斗的,为了避免牡牛闹出乱子,约翰决定任意两只牡牛之间至少要有 $K$ 只牝牛。

请计算一共有多少种排队的方法,所有牡牛可以看成是相同的,所有牝牛也一样,答案对 $5000011$ 取模。

……

READ MORE

Acwing1304 佳佳的斐波那契

原题链接:Acwing1304

题目大意:用 $S(n)$ 表示 Fibonacci 前 $n$ 项和 $mod \ m$ 的值,即 $S(n)=(f_1+f_2+…+f_n) \ mod \ m$,其中 $f_1=f_2=1,f_i=f_{i−1}+f_{i−2}$。

$T(n)=(f_1+2f_2+3f_3+…+nf_n)\ mod \ m$

已知 $n,m$,求 $T(n)$ 的值。

数据范围:$1≤n,m≤2^{31}−1$

……

READ MORE

Acwing1303 斐波那契前n项和

原题链接:Acwing1303

题目描述:大家都知道 Fibonacci 数列吧。$f_1=1,f_2=1,f_3=2,f_4=3,…,f_n=f_{n−1}+f_{n−2}$

现在问题很简单,输入 $n$ 和 $m$,求 $f_n$ 的前 $n$ 项和 $S_n \ mod \ m$。

数据范围:$1≤n≤2 \times 10^9,1≤m≤1 \times 10^9 + 10$

……

READ MORE

数论笔记

本文记录一些数论知识以及算法模板,涉及质数、约数、欧拉函数、(扩展)欧几里得、同余、乘法逆元、组合数。

……

READ MORE