题解 P4976 【毒瘤之神TM菱树-②】

NaCly_Fish · 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;
}