自动搬运

查看原文

来自洛谷，原作者为

	waaadreamer **

搬运于2025-08-24 21:46:03，当前版本为作者最后更新于2018-08-24 15:22:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这道题应该上来就能看出来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;
}