BZOJ4314 倍数?倍数!

好神仙啊....


题意

在$ [0,n) $中选$ k$个不同的数使和为$ n$的倍数

求方案数

$ n \leq 10^9, \ k \leq 10^3$


题解

k可以放大到1e6的文章来源地址:https://www.yii666.com/article/754348.html

先不考虑$ k$的限制网址:yii666.com

对答案构建多项式$ f(x)=\prod\limits_{i=0}^{n-1}(x^i+1)$文章来源地址https://www.yii666.com/article/754348.html

答案就是这个多项式所有次数为$ n$的倍数的项的系数和

考虑单位根反演

$$ans=\frac{1}{n}\sum_{i=0}^{n-1}\prod_{j=0}^{n-1}(w_n^{ij}+1)$$

设$ d=\gcd(n,i),t=\frac{n}{d}$文章地址https://www.yii666.com/article/754348.html

$$ans=\frac{1}{n}\sum_{d|n}\sum_{i=0}^{t-1}(\prod_{j=0}^{t-1}(w_t^{ij}+1))^d[\gcd(t,i)=1]$$

由于$\gcd(t,i)=1$,可以去掉单位根指数上的$ i$

$$ans=\frac{1}{n}\sum_{d|n}\sum_{i=0}^{t-1}(\prod_{j=0}^{t-1}(w_t^{j}+1))^d[\gcd(t,i)=1]$$

考虑$ \prod\limits_{j=0}^{t-1}(w_t^{j}+1)$是什么

根据定义可知$ w_t^{0..t-1}$是$ x^t-1=0$的$ n$个根

因此有$ x^t-1=\prod\limits_{i=0}^{t-1}(x-w_t^i)$网址:yii666.com<

讨论$ n$的奇偶性可得$ \prod\limits_{j=0}^{t-1}(w_t^{j}+1)=1-(-1)^t$

再用欧拉函数进行化简得$$ans=\frac{1}{n}\sum_{d|n}\phi(t)(1-(-1)^t)^d$$

然后考虑有$ k$这个限制怎么做

我们再添加一个新变量$ y$,以$ y$为主元构建多项式$ f(y)=\prod\limits_{i=0}^{n-1}(yx^i+1)$

我们要求的就是这个多项式$ y^k$的系数

用跟上面相同的方法可以化简得最后的答案多项式为$$ans=\frac{1}{n}\sum_{d|n}\phi(t)(1-(-y)^t)^d$$

由于只需要知道$y^k$的系数,直接展开就好了

跑的飞快


代码

#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#define p 1000000007
#define rt register int
#define ll long long
using namespace std;
inline ll read(){
ll x=;char zf=;char ch=getchar();
while(ch!='-'&&!isdigit(ch))ch=getchar();
if(ch=='-')zf=-,ch=getchar();
while(isdigit(ch))x=x*+ch-'',ch=getchar();return x*zf;
}
void write(ll y){if(y<)putchar('-'),y=-y;if(y>)write(y/);putchar(y%+);}
void writeln(const ll y){write(y);putchar('\n');}
int k,m,n,x,y,z,cnt,ans;
int phi[],ss[];bool pri[];
int njc[],inv[];
int ksm(int x,int y=p-){
int ans=;
for(;y;y>>=,x=1ll*x*x%p)if(y&)ans=1ll*ans*x%p;
return ans;
}
int C(int x,int y){
int ans=;
for(rt i=x;i>=x-y+;i--)ans=1ll*ans*i%p;
return 1ll*ans*njc[y]%p;
}
int main(){
n=read();k=read();phi[]=;
for(rt i=;i<=;i++)njc[i]=inv[i]=;
for(rt i=;i<=k;i++){
inv[i]=1ll*inv[p%i]*(p-p/i)%p;
njc[i]=1ll*njc[i-]*inv[i]%p;
}
for(rt i=;i<=k;i++){
if(!pri[i])ss[++cnt]=i,phi[i]=i-;
for(rt j=;j<=cnt&&i*ss[j]<=k;j++){
phi[i*ss[j]]=phi[i]*phi[ss[j]];
pri[i*ss[j]]=;
if(i%ss[j]==){
phi[i*ss[j]]=phi[i]*ss[j];
break;
}
}
}
int ans=,invn=ksm(n);
for(rt d=;d<=k;d++)if(n%d==&&k%d==){
const int v=k/d;
int tag=;
if((v&)&&(d&^))tag=-tag;
(ans+=1ll*tag*phi[d]%p*invn%p*C(n/d,k/d)%p)%=p;
}
cout<<(ans+p)%p;
return ;
}

版权声明:本文内容来源于网络,版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。文本页已经标记具体来源原文地址,请点击原文查看来源网址,站内文章以及资源内容站长不承诺其正确性,如侵犯了您的权益,请联系站长如有侵权请联系站长,将立刻删除

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信图片_20190322181744_03.jpg

微信扫一扫打赏

请作者喝杯咖啡吧~

支付宝扫一扫领取红包,优惠每天领

二维码1

zhifubaohongbao.png

二维码2

zhifubaohongbao2.png