正题

题目链接:https://loj.ac/p/6247

题目大意

给出\(n,k\)求

\[\sum_{0\leq i\leq n,i|k}\binom{n}{i}
\]

对\(998244353\)取模

\(1\leq n\leq 10^{15},1\leq k\leq 2^{20},k=2^p(p\in N)\)

解题思路

随便找的一题竟然是单位根反演，不过很基础而且很裸。

首先单位根反演的式子\([i|k]=\frac{1}{k}\sum_{j=0}^{k-1}\omega_k^{i\times j}\)

然后带到这题的式子就是

\[\sum_{i=0}^n\frac{1}{k}\sum_{j=0}^{k-1}\omega_k^{i\times j}\binom{n}{i}
\]

然后把\(j\)提出来

\[\frac{1}{k}\sum_{j=0}^{k-1}\sum_{i=0}^n(\omega_k^{i})^j\binom{n}{i}
\]

然后二项式定理

\[\frac{1}{k}\sum_{j=0}^{k-1}(\omega_k^{i}+1)^n
\]

额但是\(n\)很大直接用复数精度肯定会炸，但是\(998244353-1=2^{23}\times 7\times 17\)...又因为\(k=2^p\)，其实就是类似于\(NTT\)的思路我们直接用原根\(\omega_k^1=g^{\frac{P-1}{k}}\)就好了。

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

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const ll P=998244353;

ll n,k,ans;

ll power(ll x,ll b){

	ll ans=1;

	while(b){

		if(b&1)ans=ans*x%P;

		x=x*x%P;b>>=1;

	}

	return ans;

}

signed main()

{

	scanf("%lld%lld",&n,&k);

	ll g=power(3,(P-1)/k),z=1;

	for(ll i=0;i<k;i++,z=z*g%P)

		(ans+=power(z+1,n)%P)%=P;

	printf("%lld\n",ans*power(k,P-2)%P);

	return 0;

}

巴特西

Loj#6247-九个太阳【单位根反演】

正题

题目大意

解题思路

code

最新文章

热门文章