tyvj 1858 XLkxc

题意

给定 $k,a,n,d$ 。定义：

$$f(n)=\sum_{i=1}^ni^k $$

$$g(n)=\sum_{i=1}^nf(i) $$

求 $\left(\sum_{i=0}^ng(a+id)\right)$ 在模 $1234567891$ 意义下的值。

题解

嗟乎！逝者如流，滚滚而去！已经忘记多项式了。

总之，根据 CF622F， $f(n)$ 是 $(k+1)$ 次多项式，然后根据 $g(n)-g(n-1)=f(n)$ 知 $g(n)$ 是 $(k+2)$ 次的，同理令 $h(n)=\sum_{i=0}^ng(a+id)$ ，它是 $(k+3)$ 次的。然后拉插做。

代码

const int N = 155, mod = 1234567891;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	ll add(ll x,ll y){return 0ll+x+y>=mod?0ll+x+y-mod:x+y;}
	ll dec(ll x,ll y){return 0ll+x-y<0?0ll+x-y+mod:x-y;}
	ll mul(ll x,ll y){return 1ll*x*y%mod;}

	ll k, a, n, d;

	ll qpow (ll a, ll b) {
		ll ans = 1;
		for (; b; b >>= 1, a = mul(a, a))
			if (b & 1) ans = mul(ans, a);
		return ans;
	}

	ll fac[N], ifac[N];
	void init () {
		fac[0] = 1;
		for (int i = 1; i <= N - 5; i++) fac[i] = mul(fac[i - 1], i);
		ifac[N - 5] = qpow (fac[N - 5], mod - 2);
		for (int i = N - 6; i >= 0; i--) ifac[i] = mul(ifac[i + 1], i + 1);
	}

	ll f[N], g[N], h[N];
	ll Larange (ll *f, ll n, ll k) {
		static ll pre[N], suf[N];
		pre[0] = 1;
		for (int i = 1; i <= k; i++) pre[i] = mul(pre[i - 1], dec(n, i));
		suf[k + 1] = 1;
		for (int i = k; i; i--) suf[i] = mul(suf[i+1], dec(n, i));
		ll ans = 0;
		for(int i = 1; i <= k; i++) {
			ans = add (ans, mul(f[i], mul(mul(pre[i - 1], suf[i + 1]), mul (((k - i) & 1)? (mod - 1): 1, 
								mul(ifac[i - 1], ifac[k - i])))));
		}
		return ans;
	}

	int main () {
		init();
		for (int t = Read(); t--; ) {
			k = Read(), a = Read(), n = Read(), d = Read();
			for (int i = 1; i <= k + 3; i++) f[i] = qpow (i, k);
			for (int i = 1; i <= k + 3; i++) f[i] = add(f[i - 1], f[i]);
			for (int i = 1; i <= k + 3; i++) g[i] = add(g[i - 1], f[i]);
			for (int i = 0; i <= k + 4; i++) h[i] = Larange(g, add(a, mul(i, d)), k + 3);
			for (int i = 1; i <= k + 4; i++) h[i] = add(h[i - 1], h[i]);
			printf ("%lld\n", Larange(h, n, k + 4));
		}
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}