牛客多校第九场

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int Mod = 1000000000;
int Ksm(int a, int b, int p) {
int res = 1;
while(b) {
if(b & 1) res = 1ll * res * a % p;
a = 1ll * a * a % p;
b >>= 1;
}
return res;
}
const int maxn = 1e7+5;
int mod[2] = {512, 1953125};
int f[maxn], ans[2] = {0, 0};

int ex_gcd(int a, int b, int &x, int &y) {
if(!b) {
x = 1; y = 0;
return a;
}
int d = ex_gcd(b, a%b, x, y);
int t = x;
x = y;
y = t - a/b*y;
return d;
}

int inv(int a, int p) {
int x, y;
ex_gcd(a, p, x, y);
return (x % p + p) % p;
}

int main() {
int n, m;
scanf("%d %d", &n, &m);
for (int k = 0; k <= 1; k ++) {
int j = 2;
f[0] = 0; f[1] = 1;
for (; ; j ++) {
f[j] = (f[j-1] + f[j-2]) % mod[k];
if(f[j] == 0 && f[j-1] == 1) break;
}
for (int i = 0; i < j; i ++) {
int nr = n/j;
if(n % j >= i) nr ++;
ans[k] = (ans[k] + 1ll * Ksm(f[i], m, Mod) * nr) % mod[k];
}
}
int Inv = inv(mod[0], mod[1]);
ll res = 1ll * (ans[1] - ans[0] + Mod) % Mod * mod[0] * Inv + ans[0];
printf("%d\n", res%Mod);
return 0;
}

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int maxn = 1e5 + 7;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
typedef pair<int, int> pis;

struct T{
ll p, d;
};

ll Ksm(ll a, ll b, ll p) {
ll res = 1;
while(b) {
if(b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}

ll w;
//二次域乘法
T Mul_er(T a, T b, ll p) {
T ans;
ans.p = (a.p * b.p + a.d * b.d % p * w % p) % p;
ans.d = (a.p * b.d % p + a.d * b.p % p) % p;
return ans;
}
//二次域快速幂
T Ksm_er(T a, ll b, ll p) {
T ans;
ans.p = 1; ans.d = 0;
while(b) {
if(b & 1) ans = Mul_er(ans, a, p);
a = Mul_er(a, a, p);
b >>= 1;
}
return ans;
}
//求勒让德符号
ll Legendre(ll a, ll p) {
return Ksm(a, (p-1)>>1, p);
}

ll Recever(ll a, ll p) {
a %= p;
if(a < 0) a += p;
return a;
}

ll solve(ll n, ll p) {
if(n % p == 0) return 0;
if(p == 2) return 1;
if(Legendre(n, p) + 1 == p) return -1;
ll a = -1, t;
while(1) {
a = rand() % p;
t = a * a - n;
w = Recever(t, p);
if(Legendre(w, p) + 1 == p) break;
}
T tmp;
tmp.p = a; tmp.d = 1;
T ans = Ksm_er(tmp, (p+1)>>1, p);
return ans.p;
}

int main() {
int t;
scanf("%d", &t);
while(t --) {
ll b, c;
scanf("%lld %lld", &b, &c);
ll t = ((b * b - 4 * c) % mod + mod) % mod;
ll x = solve(t, mod);
if(x == -1) {
puts("-1 -1");
continue;
}
x = (x + b) % mod * Ksm(2, mod-2, mod) % mod;
ll y = (b - x + mod) % mod;
if(x > y) swap(x, y);
printf("%lld %lld\n", x, y);
}
return 0;
}

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
2
3
4
1: 1
2: 1 1
3: 1 2 2 1
4: 1 3 5 6 5 3 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int maxn = 1e5 + 7;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
typedef pair<int, int> pis;

ll dp[maxn], cnt[maxn], pre[maxn];

ll Ksm(ll a, ll b) {
ll res = 1;
while(b) {
if(b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}

int main() {
int n, b;
scanf("%d %d", &n, &b);
dp[0] = 1;
for (int i = 1; i < maxn; i ++) dp[i] = 1ll * dp[i-1] * b % mod;
for (int i = 1; i < maxn; i ++) dp[i] = dp[i] + dp[i-1] % mod;
pre[1] = 1;
for (int i = 2; i < maxn; i ++) pre[i] = 1ll * pre[i-1] * dp[i-1] % mod;
ll sum = pre[n];
for (int i = 1; i <= n; i ++) {
int x;
scanf("%d", &x);
cnt[x] ++;
}
for (int i = 0; i < maxn; i ++) {
if(cnt[i] > 1)
sum = 1ll * sum * Ksm(pre[cnt[i]], mod-2) % mod;
}
printf("%lld\n", sum);
return 0;
}
---------Thanks for your attention---------