牛客多校第九场

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代码

#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$下的二次剩余,模板题

#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: 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代码

#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;
}