自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 22:05:49，当前版本为作者最后更新于2019-09-29 13:01:15，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

根据 NOI2019 的教训，在做数学题时一定要试着插值一下，说不定答案是个低次多项式呢？

而这题就是这样，随便写个暴力跑一下，再写个插值，发现答案是个关于 $n$ 的一个 $6$ 次多项式。然后写出前面 $7$ 项，然后暴力插值一波就过了。

至于证明，题目中答案相关的地方没有出现形如 $n^k$ 之类的式子，所以答案肯定是关于 $n$ 的低次多项式对吧，，感性理解一下就好。

关于怎么插值，这里要用到点值 $x$ 坐标连续时的高效做法，如果不会可以来 这题 看看（

时间复杂度 $\Theta(T)$，标算为 $\Theta(T+n)$，吊打std（

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define reg register
#define p 998244853
#define K 20
using namespace std;

inline void read(int &x){
	x = 0;
	char c = getchar();
	while(c<'0'||c>'9') c = getchar();
	while(c>='0'&&c<='9'){
		x = (x<<3)+(x<<1)+(c^48);
		c = getchar();
	}
}

void print(int x){
	if(x>9) print(x/10);
	putchar(x%10+'0');
}

inline int power(int a,int t){
	int res = 1;
	while(t){
		if(t&1) res = (ll)res*a%p;
		a = (ll)a*a%p;
		t >>= 1;
	}
	return res;
}

inline int add(int a,int b){
	return a+b>=p?a+b-p:a+b;
}

inline int dec(int a,int b){
	return a<b?a-b+p:a-b;
}

const int a[8] = {0,0,4,43,225,812,2324,5670};
int pre[K],suf[K],ifac[K];

inline int solve(int n){
	if(n<8) return a[n];
	int res = 0,g;
	pre[0] = suf[8] = 1;
	for(reg int i=1;i<8;++i) pre[i] = (ll)pre[i-1]*(n-i)%p;
	for(reg int i=7;i>=1;--i) suf[i] = (ll)suf[i+1]*(n-i)%p;
	for(reg int i=1;i<8;++i){
		g = (ll)a[i]*ifac[i-1]%p*ifac[7-i]%p*pre[i-1]%p*suf[i+1]%p;
		if((7-i)&1) res = dec(res,g);
		else res = add(res,g);
	}
	return res;
}

int main(){
	ifac[0] = ifac[1] = 1;
	for(reg int i=2;i<K;++i) ifac[i] = (ll)ifac[i-1]*i%p;
	ifac[K-1] = power(ifac[K-1],p-2);
	for(reg int i=K-2;i>1;--i) ifac[i] = (ll)ifac[i+1]*(i+1)%p;
	int T,n;
	read(T);
	while(T--){
		read(n);
		print(solve(n));
		putchar('\n');
	}    
    return 0;
}