Loj#6247. 九个太阳

Loj#6247. 九个太阳

题解

前置知识

原根

二项式定理

单位根

题目

给定 $n,K$，满足$K$ 是 $2$ 的幂，求

$$\sum_{K\mid i, 0 \le i \le n} \dbinom{n}{i}$$

对 $998244353$ 取模 。

$1 \le n \le 10^{15}, 1\le K \le 2^{20}$ ， 且 $K$ 为$2$ 的幂 。

思路

首先将式子写为 ：

$$\sum_{i=0}^n \dbinom{n}{i} [K \mid i]$$

然后观察式子中的条件🤔 ，可以用单位根反演 ：

$$\frac{1}{n} \sum_{i=0}^{n-1} \omega_n^{x \ast i} = [x \bmod n =0]$$

化简式子为 ：

$$\begin{aligned} \sum_{i=0}^n \dbinom{n}{i} [K \mid i] &=\sum_{i=0}^n \frac{1}{K} \sum_{j=0}^{K-1} \omega_n^{i \ast j} \dbinom{n}{i}\\ &=\frac{1}{K} \sum_{i=1}^{n} \sum_{j=0}^{K-1} \omega_n^{i \ast j} \dbinom{n}{i}\\ &=\frac{1}{K} \sum_{j=0}^{K-1} \sum_{i=0}^n (\omega_n^{j})^i \dbinom{n}{i} \end{aligned}$$

然后观察后面的式子，对其使用二项式定理！

$$(a+b)^n = \sum_{i=0}^n \dbinom{n}{i} a^i b^{n-i}$$

拆分为 ：

$$\begin{aligned} \frac{1}{K} \sum_{j=0}^{K-1} \sum_{i=0}^n (\omega_n^{j})^i \dbinom{n}{i} &=\frac{1}{K} \sum_{j=0}^{K-1} (1+\omega_n^j)^n \end{aligned}$$

计算时由于 $998244353 = 2^{23} \times 17 \times 7 +1$ 刚好存在原根 $3$

998244353最优美的性质莫过于它是个完美恶臭数：998244353=( 114514 * ( 54-1+114 * (1+14*5+1+4) ) ) + ( 4+11451 * (4-1-15+14) ) + ( 11+41*54 + (141+541) ) + (4-1-15+14)；之所以称为完美，如果您仔细观察，您会发现每一个括号里114514都出现了正整数次！

将 $\omega_n$ 设为 $3^{\frac{p-1}{K}}$ 即可

时间复杂度 $O(n \log n)$

代码

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int mod=998244353;
ll ans;
ll qpow(ll a,ll b,ll mod)
{
    ll t=1;
    while(b!=0)
    {
        if(b&1)t=(t*a)%mod;
        a=(a*a)%mod;b>>=1;
    }
    return t;
}
ll inv(ll x){return (qpow(x,mod-2,mod)+mod)%mod;}
int main()
{
    ll n,k;
    scanf("%lld%lld",&n,&k);
    ll wn=qpow(3,(mod-1)/k,mod);
    for(ll i=0,c=1;i<k;i++,c=c*wn%mod)
    {
        ans=(ans+qpow(1+c,n,mod))%mod;
    }
    printf("%lld",(ans*inv(k)%mod+mod)%mod);
    return 0;
}