【XR-2】约定题解

NaCly_Fish · 2019-05-29 22:10:04 · 题解

【XR-2】约定题解

先说句闲话（雾）

验题人 EntropyIncreaser 对这题是这么说的：“虽然比较裸，但是还是需要比较有经验啊”。

出题人只会出裸题，菜爆了 qaq

题目大意

前置知识

期望
生成树
拉格朗日插值
线性求逆元

题解

一个无向完全图有 n^{n-2} 棵生成树，总共就有 (n-1)n^{n-2} 条边。而完全图中一共有 \frac{n(n-1)}{2} 条边，可以发现，每条边在生成树中均出现 2n^{n-3} 次。

于是我们可以推出一个式子：

\large ans=\frac{2n^{n-3}}{n^{n-2}}\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^n(i+j)^k=\frac{2}{n}\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^n(i+j)^k

这样就可以暴力计算，预处理一下自然数k次幂，就可以做到 \Theta(n^2) 了。

但是这样显然是不够优秀的，我们考虑优化。

设：

\large a_n=\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^n(i+j)^k

那么做一下差分

\large a_{n}-a_{n-1}=\sum\limits_{i=n+1}^{2n-1}i^k

然后这样就能 \Theta(n\log k) 来搞，但还是太慢。

注意到 a_n 关于 n 是一个多项式，稍微冷静分析一下，就发现这是 k+2 次的。

看到这里，很显然需要用拉格朗日插值了。不过我们可以连续取值，直接算出前 k 项的复杂度为 \Theta(k\log k)，插值的地方是 \Theta(k) 的。

然而还是不能通过，考虑继续优化。

对于这样一个函数：

\large f(x)=x^k

显然它是个完全积性函数，可以用线性筛 \Theta(k) 算出 [1,k] 中所有 f(x) 的值。

复杂度的证明很简单，小于 k 的质数约为 \lfloor k/\ln k \rfloor 个，做一次快速幂的是 \Theta(\log k)。而快速幂只会在筛到质数的时候做，所以复杂度为 \Theta((k/\log k)\times\log k)=\Theta(k)。

最后就是我们在做拉格朗日插值时，会用到求逆元。如果用快速幂或 exgcd 来求的话，还是会比较慢。

所以用一下【模板】乘法逆元2 的套路，线性求一波即可。

~~当然你也可以用前后缀积直接解决。~~

把算出来的 a_n 乘 2 再除以 n 即是答案。

代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 20000007
#define p 998244353
#define ll long long
#define reg register
using namespace std;

inline void read(int &x);
void print(int x);
inline int power(int a,int t);
int solve();

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

int n,k,lim,ans,cnt;
int f[N],s[N],inv[N],fac[N];

int main(){
    read(n),read(k);
    lim = min((k+3),n+1)<<1;
    s[1] = 1;
    for(reg int i=2;i<=lim;++i){
        if(!s[i]){
            f[++cnt] = i;
            s[i] = power(i,k);
        }
        for(reg int j=1;j<=cnt&&i*f[j]<=lim;++j){
            s[i*f[j]] = (ll)s[i]*s[f[j]]%p;
            if(i%f[j]==0) break;
        }
    }
    for(reg int i=2;i<=lim;++i) s[i] = add(s[i],s[i-1]);
    lim >>= 1;
    f[1] = 0;
    f[2] = power(3,k);
    for(reg int i=3;i<=lim;++i)
        f[i] = add(f[i-1],dec(s[(i<<1)-1],s[i]));
    if(n<=lim) ans = f[n];
    else ans = solve();
    ans = (ll)(ans<<1)*power(n,p-2)%p;
    print(ans);
    return 0;
}

int solve(){
    s[0] = s[1] = 1;
    for(reg int i=2;i<=lim;++i)
        s[i] = (ll)s[i-1]*i%p;
    fac[0] = 1;
    reg int g,mul = 1,res = 0;
    for(reg int i=1;i<=lim;++i){
        mul = (ll)mul*(n-i)%p;
        inv[i] = fac[i] = (ll)s[i-1]*s[lim-i]%p*(n-i)%p;
    }
    for(reg int i=2;i<=lim;++i)
        fac[i] = (ll)fac[i-1]*fac[i]%p;
    fac[lim] = power(fac[lim],p-2);
    for(reg int i=lim;i>=1;--i){
        g = inv[i];
        inv[i] = (ll)fac[i-1]*fac[i]%p;
        fac[i-1] = (ll)g*fac[i]%p;
    }
    for(reg int i=1;i<=lim;++i){
        g = (ll)f[i]*mul%p*inv[i]%p;
        if((lim-i)&1) g = (ll)g*(p-1)%p;
        res = add(res,g);
    }   
    return res;
}

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 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');
}

拓展

以上都是在 n\neq 998244353 的前提下讨论的。

而对于 n = 998244353 这种特殊情况，这里就多扯一句。

首先容易证明插值出来的这个多项式，常数项为 0。

要求的答案是 \large \frac{2a_n}{n} \mod n ，相当于求 2\times[n^1]a_n。

那么只要求出其一次项系数乘 2，就是答案了。

由于只用求一次项，所以可以按照二项式的方法来算，更高次的直接忽略掉，对答案没有影响。

还有就是预处理一下二项式的前后缀积，做法和前面的很类似。

\large f(x)=\sum\limits_{i=1}^n\frac{f(i)(-1)^{n-i}}{(i-1)!(n-i)!}\prod_{j\neq i}(x-j)

这个式子就是前半部分把阶乘逆元预处理好，后半部分就是刚才说的前后缀积处理。

两种情况的时间复杂度都为 \Theta(k)。

对了，既然此题是用的小圆作为题面，那就在题解的最后放上一张图吧~

【XR-2】约定 题解