题解 P3169 【[CQOI2015]多项式 】

· · 题解

这道题应该上来就能看出来a肯定是个有循环节的玩意儿……结果我上来打了个表瞄了一眼，以为循环节长度就是3389（我真的太菜了），然后无限WA……后来才发现原来循环节长度是3388……Orz……

于是就可以开始推算式了，考虑展开：

\sum_{k=0}^nb_k(x-t)^k=\sum_{k=0}^nb_k\sum_{i=0}^k(-1)^{k-i}t^{k-i}x^i\binom ki

显然可以交换求和顺序，于是乎

=\sum_{i=0}^nx^i\sum_{k=i}^n\binom kib_k(-1)^{k-i}t^{k-i}

然后就得到了

a_i=\sum_{k=i}^nb_k(-1)^{k-i}t^{k-i}\binom ki

这是一个裸的二项式反演，于是就可以得到

b_k=\sum_{i=k}^n(-1)^{i-k}\binom ika_it^{i-k}

然后发现题目中的条件n-m\le 5，暴力高精度算一下就没了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1 << 15 | 5;
const double PI = acos(-1);
struct C{
    double x, y;
    C operator+(const C &c) const {return (C){x + c.x, y + c.y};}
    C operator-(const C &c) const {return (C){x - c.x, y - c.y};}
    C operator*(const C &c) const {return (C){x * c.x - y * c.y, x * c.y + y * c.x};}
} aa[maxn], tab[maxn];
void rader(C *a, int n){
    for(int i = 1, j = n >> 1; i < n - 1; i++){
        if(i < j) swap(a[i], a[j]);
        int k = n >> 1;
        for(; j >= k; k >>= 1) j -= k;
        if(j < k) j += k;
    }
}
void fft(C *a, int n){
    rader(a, n);
    for(int h = 2; h <= n; h <<= 1){
        int hh = h >> 1;
        for(int i = 0; i < n; i += h)
        for(int j = i; j < i + hh; j++){
            C x = a[j], y = a[j + hh] * tab[n / h * (j - i)];
            a[j] = x + y, a[j + hh] = x - y;
        }
    }
}
struct Bigint{
    int a[maxn], n;
    Bigint(){memset(a, 0, sizeof(a)); n = 0;}
    Bigint(char *str){
        memset(a, 0, sizeof(a));
        int l = strlen(str);
        n = 0;
        for(int i = l - 1; i >= 0; i -= 4, ++n){
            for(int j = max(i - 3, 0); j <= i; j++)
                a[n] = a[n] * 10 + str[j] - '0';
        }
    }
    Bigint operator*(const Bigint &b) const {
        Bigint res = Bigint();
        for(res.n = 1; res.n < n + b.n; res.n <<= 1);
        for(int i = 0; i < res.n; i++){
            aa[i] = (C){a[i], b.a[i]};
            tab[i] = (C){cos(2 * i * PI / res.n), sin(2 * i * PI / res.n)};
        }
        fft(aa, res.n);
        for(int i = 0; i < res.n; i++){
            aa[i] = aa[i] * aa[i];
            tab[i].y = -tab[i].y;
        }
        fft(aa, res.n);
        for(int i = 0; i < res.n; i++) aa[i].y /= 2 * res.n;
        for(int i = 0; i < res.n; i++){
            ll t = (ll)(aa[i].y + 0.5);
            res.a[i] = t % 10000;
            aa[i + 1].y += t / 10000;
        }
        if(aa[res.n].y > 0.5) res.a[res.n++] = (int)(aa[res.n].y + 0.5);
        while(res.n > 0 && !res.a[res.n - 1]) --res.n;
        return res;
    }
    Bigint operator+(const Bigint &b) const {
        Bigint res = Bigint();
        res.n = max(n, b.n);
        for(int i = 0; i < res.n; i++){
            res.a[i] += a[i] + b.a[i];
            if(res.a[i] >= 10000) ++res.a[i + 1], res.a[i] -= 10000;
        }
        if(res.a[res.n]) ++res.n;
        return res;
    }
    Bigint operator*(int b) const {
        Bigint res = Bigint();
        for(int i = 0; i < n; i++){
            ll t = (ll)a[i] * b + res.a[i];
            res.a[i] = t % 10000;
            res.a[i + 1] = t / 10000;
        }
        for(res.n = n; res.a[res.n]; ++res.n){
            res.a[res.n + 1] = res.a[res.n] / 10000;
            res.a[res.n] %= 10000;
        }
        return res;
    }
    Bigint operator/(int b) const {
        Bigint res = Bigint();
        res.n = n;
        for(int i = n - 1; i >= 0; i--){
            int t = res.a[i] + a[i];
            if(i > 0) res.a[i - 1] += t % b * 10000;
            res.a[i] = t / b;
        }
        while(res.n > 0 && !res.a[res.n - 1]) --res.n;
        return res;
    }
    int operator%(int b) const {
        int res = 0;
        for(int i = n - 1; i >= 0; i--)
            res = (res * 10000 + a[i]) % b;
        return res;
    }
    Bigint operator-(const Bigint &b) const {
        Bigint res = Bigint();
        for(int i = 0; i < n; i++){
            res.a[i] += a[i] - b.a[i];
            if(res.a[i] < 0) res.a[i] += 10000, --res.a[i + 1];
        }
        for(res.n = n; res.n > 0 && !res.a[res.n - 1]; --res.n);
        return res;
    }
    Bigint& operator++(){
        ++a[0];
        for(int i = 0; i < n; i++){
            if(a[i] >= 10000) ++a[i + 1], a[i] -= 10000;
            else break;
        }
        if(a[n]) ++n;
        return *this;
    }
    void print(){
        printf("%d", a[n - 1]);
        for(int i = n - 2; i >= 0; i--) printf("%04d", a[i]);
        putchar('\n');
    }
    int cmp(const Bigint &b) const {
        if(n != b.n) return n < b.n ? -1 : 1;
        for(int i = n - 1; i >= 0; i--)
            if(a[i] != b.a[i]) return a[i] < b.a[i] ? -1 : 1;
        return 0;
    }
    bool operator>=(const Bigint &b) const {return cmp(b) >= 0;}
} n, m, mul, res;
char str[maxn];
int a[3500], vis[3500], K;
int main(){
    vis[a[0] = 1] = 1;
    for(int i = 1; i < 3388; i++)
        a[i] = (1234 * a[i - 1] + 5678) % 3389;
    scanf("%s", str);
    n = Bigint(str);
    scanf("%d", &K);
    scanf("%s", str);
    m = Bigint(str);
    int sub = (n - m).a[0], mod = m % 3388;
    mul.n = mul.a[0] = 1;
    for(int i = 0; i <= sub; i++){
        res = res + mul * a[mod];
        mul = mul * (++m) * K / (i + 1);
        mod = (mod + 1) % 3388;
    }
    res.print();
    return 0;
}