题解

令x = x - t代换一下会发现

\(\sum_{i = 0}^{n}a_i (x + t)^i = \sum_{i = 0}^{n} b_{i} x^{i}\)

剩下的就需要写高精度爆算了……

代码

#include 
    
     #define enter putchar('\n')#define space putchar(' ')#define pii pair
     
      #define fi first#define se second#define mp make_pair#define pb push_back#define eps 1e-8//#define ivorysiusing namespace std;typedef long long int64;typedef double db;template
      
       void read(T &res) {    res = 0;T f = 1;char c = getchar();    while(c < '0' || c > '9') {        if(c == '-') f = -1;        c = getchar();    }    while(c >= '0' && c <= '9') {        res = res * 10 - '0' + c;        c = getchar();    }    res *= f;}template
       
        void out(T x) {    if(x < 0) {x = -x;putchar('-');}    if(x >= 10) out(x / 10);    putchar('0' + x % 10);}int BASE = 100000000;int len = 8;struct Bignum {    vector
        
          v;    Bignum(int64 x = 0) {        *this = x;    }    Bignum operator = (int64 x) {        v.clear();        do {            v.pb(x % BASE);            x /= BASE;        }while(x);        return *this;    }    Bignum operator = (string str) {        v.clear();int x;        for(int i = str.length() ; i > 0 ; i -= len) {            int st = max(0,i - len),ed = i;            sscanf(str.substr(st,ed - st).c_str(),"%d",&x);            v.pb(x);        }        return *this;    }    friend Bignum operator + (const Bignum &a,const Bignum &b) {        Bignum c;c.v.clear();        int x,g = 0,p = 0;        while(1) {            x = g;            if(p < a.v.size()) x += a.v[p];            if(p < b.v.size()) x += b.v[p];            if(!x && p >= a.v.size() && p >= b.v.size()) break;            g = x / BASE;            c.v.pb(x % BASE);            ++p;        }        return c;    }    friend Bignum operator - (const Bignum &a,const Bignum &b) {        Bignum c;c.v.clear();        int x,g = 0,p = 0;        while(1) {            x = -g;g = 0;            if(p < a.v.size()) x += a.v[p];            if(p < b.v.size()) x -= b.v[p];            if(!x && p >= a.v.size() && p >= b.v.size()) break;            if(x < 0) {x += BASE;g = 1;}            c.v.pb(x);            ++p;        }        return c;    }    friend Bignum operator * (const Bignum &a,const Bignum &b) {        Bignum c;c.v.clear();        c.v.resize(a.v.size() + b.v.size());        int64 x,g = 0;        for(int i = 0 ; i < a.v.size() ; ++i) {            g = 0;            for(int j = 0 ; j < b.v.size() ; ++j) {                x = 1LL * a.v[i] * b.v[j] + g + c.v[i + j];                c.v[i + j] = x % BASE;                g = x / BASE;            }            int t = i + b.v.size();            while(g) {                x = g + c.v[t];                c.v[t] = x % BASE;                g = x / BASE;                ++t;            }        }        for(int i = c.v.size() - 1 ; i > 0 ; --i) {            if(!c.v[i]) c.v.pop_back();            else break;        }        return c;    }    friend Bignum operator / (const Bignum &a,const int &d) {        Bignum c;        c.v.resize(a.v.size());        int64 x = 0,t;        for(int i = a.v.size() - 1 ; i >= 0 ; --i) {            t = 1LL * x * BASE + a.v[i];            c.v[i] = t / d;            x = t % d;        }        for(int i = c.v.size() - 1 ; i > 0 ; --i) {            if(!c.v[i]) c.v.pop_back();            else break;        }        return c;    }    void print() {        int s = v.size() - 1;        printf("%d",v[s]);        --s;        for(int i = s ; i >= 0 ; --i) {            printf("%08d",v[i]);        }    }}N,M,T,C,B,tmp;string s[4];struct Matrix {    int f[2][2];    Matrix(){memset(f,0,sizeof(f));}    friend Matrix operator * (const Matrix &a,const Matrix &b) {        Matrix c;        for(int i = 0 ; i <= 1 ; ++i) {            for(int j = 0 ; j <= 1 ; ++j) {                for(int k = 0 ; k <= 1 ; ++k) {                    c.f[i][j] = (c.f[i][j] + a.f[i][k] * b.f[k][j]) % 3389;                }            }        }        return c;    }}A[15],ans;int64 a[15],num[100005];int64 fpow(int64 x,int64 c) {    int64 res = 1,t = x;    while(c) {        if(c & 1) res = 1LL * res * t % 3389;        t = 1LL * t * t % 3389;        c >>= 1;    }    return res;}int main() {#ifdef ivorysi    freopen("f1.in","r",stdin);#endif    cin>>s[0]>>s[1]>>s[2];    N = s[0];T = s[1],M = s[2];    A[0].f[0][0] = A[0].f[1][1] = 1;    A[1].f[0][0] = 1234,A[1].f[0][1] = 5678 % 3389,A[1].f[1][1] = 1;    ans = A[0];    for(int i = 2 ; i <= 10 ; ++i) A[i] = A[i - 1] * A[1];    int c = (N - M).v[0];    for(int i = 0 ; i < s[0].length() ; ++i) {        Matrix t = A[0];        for(int j = 1 ; j <= 10 ; ++j) t = t * ans;        ans = t * A[s[0][i] - '0'];    }    a[0] = (ans.f[0][0] + ans.f[0][1]) % 3389;    int64 inv = fpow(1234,3389 - 2);    for(int i = 1 ; i <= c ; ++i) a[i] = 1LL * (a[i - 1] - 5678 + 3389 * 2) * inv % 3389;    tmp = C = 1;    for(int i = c; i >= 0 ; --i) {        B = B + tmp * C * a[i];        tmp = tmp * T;        M = M + 1;        C = C * M;        C = C / (c - i + 1);    }    B.print();enter;}