好神仙啊....
题意
在$ [0,n) $中选$ k$个不同的数使和为$ n$的倍数
求方案数
$ n \leq 10^9, \ k \leq 10^3$
题解
k可以放大到1e6的
先不考虑$ k$的限制
对答案构建多项式$ f(x)=\prod\limits_{i=0}^{n-1}(x^i+1)$
答案就是这个多项式所有次数为$ 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}$
$$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)$
讨论$ 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#include #include #include #include #include #include #include #define p 1000000007#define rt register int#define ll long longusing namespace std;inline ll read(){ ll x=0;char zf=1;char ch=getchar(); while(ch!='-'&&!isdigit(ch))ch=getchar(); if(ch=='-')zf=-1,ch=getchar(); while(isdigit(ch))x=x*10+ch-'0',ch=getchar();return x*zf;}void write(ll y){ if(y<0)putchar('-'),y=-y;if(y>9)write(y/10);putchar(y%10+48);}void writeln(const ll y){write(y);putchar('\n');}int k,m,n,x,y,z,cnt,ans;int phi[1010],ss[1010];bool pri[1010];int njc[1010],inv[1010];int ksm(int x,int y=p-2){ int ans=1; for(;y;y>>=1,x=1ll*x*x%p)if(y&1)ans=1ll*ans*x%p; return ans;}int C(int x,int y){ int ans=1; for(rt i=x;i>=x-y+1;i--)ans=1ll*ans*i%p; return 1ll*ans*njc[y]%p;}int main(){ n=read();k=read();phi[1]=1; for(rt i=0;i<=1;i++)njc[i]=inv[i]=1; for(rt i=2;i<=k;i++){ inv[i]=1ll*inv[p%i]*(p-p/i)%p; njc[i]=1ll*njc[i-1]*inv[i]%p; } for(rt i=2;i<=k;i++){ if(!pri[i])ss[++cnt]=i,phi[i]=i-1; for(rt j=1;j<=cnt&&i*ss[j]<=k;j++){ phi[i*ss[j]]=phi[i]*phi[ss[j]]; pri[i*ss[j]]=1; if(i%ss[j]==0){ phi[i*ss[j]]=phi[i]*ss[j]; break; } } } int ans=0,invn=ksm(n); for(rt d=1;d<=k;d++)if(n%d==0&&k%d==0){ const int v=k/d; int tag=1; if((v&1)&&(d&1^1))tag=-tag; (ans+=1ll*tag*phi[d]%p*invn%p*C(n/d,k/d)%p)%=p; } cout<<(ans+p)%p; return 0;}