$\sum_{k = 0} ^ {n} a_kx^k = \sum_{k = 0} ^ {n} b_k(x - t)^k \Leftrightarrow \sum_{k = 0} ^ {n} a_k(x + t)^k = \sum_{k = 0} ^ {n} b_kx^k$
把式子左边用二项式定理展开：
$b_m=\sum_{k=m}^nC_k^{k-m}t^{k-m}a_k\\=\sum_{k=0}^{n-m}C_{m+k}^k t^k a_{m+k}$
注意到$n - m \leq 5$，然后。。。然后就没有然后了
出题人都是*****！
/**************************************************************
Problem: 3933
User: rausen
Language: C++
Result: Accepted
Time:324 ms
Memory:1148 kb
****************************************************************/ #include <cstdio>
#include <cstring>
#include <algorithm> using namespace std;
typedef long long ll;
const int Len = 2e3 + ;
const int N = 3e3 + ;
const ll base = 1e9;
const int mod = ; inline void print(int t, bool f); struct Big {
ll x[Len];
int len;
Big(ll _ = ) {
memset(x, , sizeof(x));
x[len = ] = _;
} inline ll& operator [] (int i) {
return x[i];
} inline void get() {
static char st[N];
static int i, l, tmp;
memset(x, , sizeof(x));
gets(st + ), l = strlen(st + );
for (i = l; i; --i) {
if ((l - i) % == ) tmp = ;
x[(l - i) / + ] += 1ll * (st[i] - '') * tmp, tmp *= ;
}
len = (l - ) / + ;
}
inline void put(char ch = '\n') {
static int i;
for (print(x[len], ), i = len - ; i; --i)
print(x[i], );
putchar(ch);
} inline Big operator + (const Big &b) const {
static Big res;
static int i;
res = , res.len = max(len, b.len);
for (i = ; i <= res.len; ++i) {
res[i] += x[i] + b.x[i];
if (res[i] >= base)
res[i] -= base, ++res[i + ];
}
if (res[res.len + ]) ++res.len;
while (!res[res.len]) --res.len;
return res;
}
inline Big& operator += (const Big &b) {
return *this = *this + b;
}
inline Big& operator ++() {
return *this += ;
} inline ll operator - (const Big &b) {
static int i;
static ll res;
for (res = , i = len; i; --i)
res = res * base + x[i] - b.x[i];
return res;
} inline Big operator * (const Big &b) const {
static Big res;
static int i, j;
res = , res.len = len + b.len;
for (i = ; i <= len; ++i)
for (j = ; j <= b.len; ++j) {
res[i + j - ] += x[i] * b.x[j];
res[i + j] += res[i + j - ] / base, res[i + j - ] %= base;
}
for (i = ; i <= res.len; ++i)
res[i + ] += res[i] / base, res[i] %= base;
while (!res[res.len] && res.len) --res.len;
if (!res.len) res.len = ;
return res;
}
inline Big& operator *= (const Big &b) {
*this = *this * b;
} inline Big operator / (int t) const {
static Big res;
static int i;
res = *this;
for (i = len; i; --i)
res[i - ] += (res[i] % t) * base, res[i] /= t;
res[] = ;
while (!res[res.len] && res.len) --res.len;
if (!res.len) res.len = ;
return res;
}
inline Big& operator /= (int t) {
return *this = *this / t;
} ll operator % (int t) const {
static int i;
static ll res;
for (res = , i = len; i; --i)
res = (res * base + x[i]) % t;
return res;
}
} n, m, ans, C, p, t; inline int pow(int x, int y) {
static int res;
res = ;
while (y) {
if (y & ) res = res * x % mod;
x = x * x % mod, y >>= ;
}
return res;
} inline int A(const Big &t) {
return ( * pow(, t % (mod - )) + ) % mod;
} int main() {
int i, tmp;
n.get(), t.get(), m.get();
tmp = n - m, C = p = , ans = ;
for (i = ; i <= tmp; ++i, ++m) {
if (i) C = (C * m) / i, p *= t;
ans += C * p * A(m);
}
ans.put();
return ;
} inline void print(int t, bool f) {
static int tmp, tot, pr[];
if (t < ) putchar('-'), tmp = -t;
else tmp = t;
tot = ;
while (tmp)
pr[++tot] = tmp % , tmp /= ;
if (f) for (tmp = - tot; tmp; --tmp) putchar('');
while (tot) putchar(pr[tot--] + '');
}