存在式子
\[n\cdot [n|k]=\sum_{i=0}^{n-1}\omega_n^{ik}\\ \]我们考虑来证明一下，
- 若 \([n|k]=1\) ，那么显然 \(\omega_n^{ik}=1\) 。
- 若 \([n|k]\ne 1\) ，那么后者就是一个等比数列，我们运用求和公式 \(\frac{\omega_n^{nk}-1}{\omega_n^k-1}=0\) 。
我们可以利用这个式子提取出一个多项式的整数倍系数。
\[\sum_{i=0}^{\lfloor\frac{n}{k}\rfloor}[x^{ik}]f(x)=\sum_{i=0}^n[k|i][x^i]f(x)\\ =\sum_{i=0}^n(\frac{1}{k}\sum_{j=0}^{k-1}\omega_k^{ij})[x^i]f(x)\\ =\frac{1}{k}\sum_{j=0}^{k-1}\sum_{i=0}^n\omega_k^{ij}\cdot [x^i]f(x)\\ =\frac{1}{k}\sum_{j=0}^{k-1}\sum_{i=0}^n(\omega_k^{j})^i\cdot [x^i]f(x)\\ =\frac{1}{k}\sum_{j=0}^{k-1}f(w_k^j)\\ \]LOJ6485 LJJ 学二项式定理
求
\[\sum_{i=0}^n(\binom{n}{i}\cdot s^i\cdot a_{i\bmod4})\\ \]我们考虑由于 \(i\) 在不同位数下的取值与 \(\bmod 4\) 的值有关，所以我们想到单位根反演。所以我们先定义多项式并尝试将其化简。
\[f(x)=\sum_{i=0}^nx^i\cdot\binom{n}{i}\cdot s^i=(xs+1)^n\\ \]然后我们考虑到单位根反演只能求整数倍，但是我们这里还需要求存在余数的情况，可以比较容易地想到平移。
\[\text{res}=\frac{1}{k}\sum_{i=0}^{k-1}a_i\sum_{j=0}^{k-1}\frac{(s\omega_k^j+1)^n}{\omega_k^{ij}}\\ \]尼玛 for 循环写错调半天。
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353,K=4,INVK=748683265;
const int w[K]={1,911660635,998244352,86583718};
const int _w[K]={1,86583718,998244352,911660635};
int ADD(int x,int y){return x+y>=MOD?x+y-MOD:x+y;}
int SUB(int x,int y){return x-y<0?x-y+MOD:x-y;}
int TIME(int x,int y){return (int)(1ll*x*y%MOD);}
int ksm(int x,int k=MOD-2){int res=1;for(;k;k>>=1,x=TIME(x,x))if(k&1)res=TIME(res,x);return res;}
long long n;int s,a[4],res;
int solve(){
scanf("%lld%d",&n,&s),res=0;
for(int i=0;i<K;++i){
int sum=0;scanf("%d",&a[i]);
for(int j=0;j<K;++j)
sum=ADD(sum,TIME(ksm(ADD(TIME(s,w[j]),1),n%(MOD-1)),_w[i*j%K]));
res=ADD(res,TIME(sum,a[i]));
}
return res=TIME(res,INVK),printf("%d\n",res),0;
}
int main(){
int T;cin>>T;while(T--) solve();
return 0;
}
UOJ450 【集训队作业2018】复读机
这个不会是什么 \(k\) 元生成函数吧。。。
我们貌似可以得到这么一个奇怪的式子，
\[\text{res}=\sum_{a=0}^{d-1}\sum_{b=0}^{d-1}\sum_{c=0}^{d-1}\cdots f(w_d^a,w_d^b,w_d^c,\cdots)\\ =\sum_{a=0}^{d-1}\sum_{b=0}^{d-1}\sum_{c=0}^{d-1}\cdots (w_d^a+w_d^b+w_d^c+\cdots)^n\\ \]#include<bits/stdc++.h>
using namespace std;
const int K=500005;
const int MOD=19491001,W2=19491000,W3=18827933;
int ADD(int x,int y){return x+y>=MOD?x+y-MOD:x+y;}
int TIME(int x,int y){return (int)(1ll*x*y%MOD);}
int ksm(int x,int k=MOD-2){int res=1;for(;k;k>>=1,x=TIME(x,x))if(k&1)res=TIME(res,x);return res;}
int n,k,d;
int fact[K],ifact[K];
void init(){
fact[0]=1;
for(int i=1;i<=k;++i) fact[i]=TIME(fact[i-1],i);
ifact[k]=ksm(fact[k]);
for(int i=k;i>=1;--i) ifact[i-1]=TIME(ifact[i],i);
}
int main(){
cin>>n>>k>>d;
if(d==1) return printf("%d\n",ksm(k,n)),0;
init();int res=0;
if(d==2){
for(int i=0;i<=k;++i){
int tmp=TIME(fact[k],TIME(ifact[i],ifact[k-i]));
res=ADD(res,TIME(tmp,ksm(ADD(i,TIME(k-i,W2)),n)));
}
return printf("%d\n",TIME(res,ksm(ksm(d),k))),0;
}
if(d==3){
for(int i=0;i<=k;++i){
for(int j=0;i+j<=k;++j){
int tmp=TIME(fact[k],TIME(ifact[i],TIME(ifact[j],ifact[k-i-j])));
res=ADD(res,TIME(tmp,ksm(ADD(i,ADD(TIME(j,W3),TIME(k-i-j,ksm(W3,2)))),n)));
}
}
return printf("%d\n",TIME(res,ksm(ksm(d),k))),0;
}
}