A: The Power of Fibonacci
题意
给你n,m,求$\sum\limits_{i=1}^{n}F_i^m \mod 1e9,F$是斐波那契数列
思路
首先斐波那契数列在模意义下是有循环节的,而在$1e9$下的循环节有太大,
所以我们把$1e9$分为两个互质数字的乘积$512*1953125$,而在这两个模下的循环节是可以接受的
然后我们分别算出一个结果用中国剩余定理求出答案就行了
注意快速幂模的时候有模$1e9$不然会T,可能是别的模数取模次数太多造成的超时
做完我傻了
AC代码
1 |
|
B: Quadratic equation
题意
$x+y\equiv b\mod p, x\cdot y\equiv c \mod p$
求$x,y$
思路
二次剩余基础题,可惜我不会
根据初中知识我们可以化成这样$(x-\frac{b}{2})^2\equiv \frac{b^2-4c}{4} \mod p$
下面就是验证$\frac{b^2-4c}{4}$是否是模$p$下的二次剩余,模板题
1 |
|
C: Inversions of all permutations
题意
$\sum\limits_{r_i is a permutation of {a_i}}b^{t(r_i)}\mod 1e9+7$
求$b$的序列$a$的全排列的逆序对次幂之和
思路
对于一个没有重复数字的序列,其逆序数为
1 | 1: 1 |
3:1 2 2 1
代表长度为$3$的序列的逆序数为$0$的有$1$个,逆序数为$1$的有$2$个,逆序数为$3$的有$2$个,逆序数为$3$的有$3$个
我们用$dp$来代表答案,那么长度为$3$的答案就是$dp[3]=b^0+2b^1+2b^2+b^3$
而$dp$转移是有规律的$dp[i] = dp[i-1]\times \sum\limits_{j=0}^{i-1}b^j$
而对于有重复数字的序列,其结果就是$\frac{dp[n]}{\prod dp[重复次数]}$
AC代码
1 |
|