传送门
考虑由于 x n = ∑ i = 0 n S 2 ( n , i ) i ! ( x i ) x^n=\sum_{i=0}^nS_2(n,i)i!{x\choose i} xn=∑i=0nS2(n,i)i!(ix)
由于 ( x i ) = ( x − 1 i − 1 ) + ( x − 1 i ) {x\choose i}={x-1\choose i-1}+{x-1\choose i} (ix)=(i−1x−1)+(ix−1)
考虑 f [ i ] [ j ] f[i][j] f[i][j]表示 ∑ u = 1 n ( d i s ( u , j ) j ) \sum_{u=1}^n{dis(u,j)\choose j} ∑u=1n(jdis(u,j))
记 u p [ i ] [ j ] up[i][j] up[i][j]表示 i i i的子树以外的点和 i i i的 d i s dis dis
d o w n [ i ] [ j ] down[i][j] down[i][j]表示子树的
以 d o w n down down为例
由于从儿子转移过来, d i s dis dis会加一
所以 d o w n [ u ] [ j ] = ∑ v = s o n [ u ] d o w n [ v ] [ j ] + d o w n [ v ] [ j − 1 ] down[u][j]=\sum_{v=son[u]}down[v][j]+down[v][j-1] down[u][j]=∑v=son[u]down[v][j]+down[v][j−1]
u p up up类似
#include<bits/stdc++.h>
using namespace std;
#define gc getchar
inline int read(){
char ch=gc();
int res=0,f=1;
while(!isdigit(ch))f^=ch=='-',ch=gc();
while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
return f?res:-res;
}
#define re register
#define pb push_back
#define cs const
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
const int mod=10007;
inline int add(int a,int b){return (a+=b)>=mod?a-mod:a;}
inline void Add(int &a,int b){(a+=b)>=mod?(a-=mod):0;}
inline int dec(int a,int b){return (a-=b)<0?a+mod:a;}
inline void Dec(int &a,int b){(a-=b)<0?(a+=mod):0;}
inline int mul(int a,int b){return 1ll*a*b>=mod?1ll*a*b%mod:a*b;}
inline void Mul(int &a,int b){a=mul(a,b);}
inline int ksm(int a,int b,int res=1){
for(;b;b>>=1,a=mul(a,a))(b&1)&&(res=mul(res,a));return res;
}
inline int Inv(int x){
return ksm(x,mod-2);
}
const int N=50005,K=155;
int up[N][K],dn[N][K];
int n,k;
vector<int> e[N];
void dfsd(int u,int fa){
dn[u][0]=1;
for(int i=0;i<e[u].size();i++){
int v=e[u][i];
if(v==fa)continue;
dfsd(v,u);
for(int j=0;j<=k;j++){
Add(dn[u][j],dn[v][j]);
if(j)Add(dn[u][j],dn[v][j-1]);
}
}
}
void dfsu(int u,int fa){
for(int i=0;i<e[u].size();i++){
int v=e[u][i];
if(v==fa)continue;
for(int j=0;j<=k;j++){
Add(up[v][j],add(up[u][j],dn[u][j])),Dec(up[v][j],dn[v][j]);
if(j)Add(up[v][j],add(dn[u][j-1],up[u][j-1])),Dec(up[v][j],add(dn[v][j-1],dn[v][j-1]));
if(j>1)Dec(up[v][j],dn[v][j-2]);
}
dfsu(v,u);
}
}
int fac[K],s[K][K];
int main(){
n=read(),k=read();
int L=read(),now=read(),A=read(),B=read(),Q=read();
for(int i=1;i<n;i++){
now=(now*A+B)%Q;int tmp=(i<L)?i:L;
int u=i-now%tmp,v=i+1;
// int u=read(),v=read();
e[u].pb(v),e[v].pb(u);
}
dfsd(1,0);
dfsu(1,0);
fac[0]=1;
for(int i=1;i<=k;i++)fac[i]=mul(fac[i-1],i);
s[0][0]=1;
for(int i=1;i<=k;i++)
for(int j=1;j<=i;j++)
s[i][j]=add(s[i-1][j-1],mul(s[i-1][j],j));
for(int i=1;i<=n;i++){
int res=0;
for(int j=1;j<=k;j++)
Add(res,mul(mul(s[k][j],fac[j]),add(up[i][j],dn[i][j])));
cout<<res<<'\n';
}
}