题目链接

BZOJ2159

题解

显然不能直接做点分之类的，观察式子中存在式子\(n^k\)

可以考虑到

发现\(k\)很小，对于每个点可以直接\(O(k)\)计算

所以我们只需求出

转移可以利用

复杂度\(O(nk + k^2)\)

最后注意一下读入是加密的，在题目末尾

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<map>

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define mp(a,b) make_pair<int,int>(a,b)

#define cls(s) memset(s,0,sizeof(s))

#define cp pair<int,int>

#define LL long long int

using namespace std;

const int maxn = 50005,maxm = 155,INF = 1000000000,P = 10007;

int f[maxn][maxm],g[maxm],n,K,fa[maxn];

int h[maxn],ne = 1;

struct EDGE{int to,nxt;}ed[maxn << 1];

inline void build(int u,int v){

	ed[++ne] = (EDGE){v,h[u]}; h[u] = ne;

	ed[++ne] = (EDGE){u,h[v]}; h[v] = ne;

}

void dfs1(int u){

	f[u][0] = 1;

	Redge(u) if ((to = ed[k].to) != fa[u]){

		fa[to] = u; dfs1(to);

		f[u][0] = f[u][0] + f[to][0];

		for (int k = 1; k <= K; k++)

			f[u][k] = (f[u][k] + f[to][k - 1] + f[to][k]) % P;

	}

}

void dfs2(int u){

	if (fa[u]){

		int v = fa[u];

		g[0] = f[v][0] - f[u][0];

		for (int k = 1; k <= K; k++)

			g[k] = ((f[v][k] - f[u][k] - f[u][k - 1]) % P + P) % P;

		f[u][0] = n;

		for (int k = 1; k <= K; k++)

			f[u][k] = (f[u][k] + g[k] + g[k - 1]) % P;

	}

	Redge(u) if ((to = ed[k].to) != fa[u])

		dfs2(to);

}

int S[maxm][maxm],ans,fac[maxm];

void work(){

	S[0][0] = 1; fac[0] = 1;

	for (register int i = 1; i <= K; i++) fac[i] = fac[i - 1] * i % P;

	for (register int i = 1; i <= K; i++)

		for (register int j = 1; j <= i; j++)

			S[i][j] = (S[i - 1][j - 1] + j * S[i - 1][j]) % P;

	for (register int i = 1; i <= n; i++){

		ans = 0;

		for (register int k = 0; k <= K; k++)

			ans = (ans + f[i][k] * fac[k] % P * S[K][k] % P) % P;

		printf("%d\n",ans);

	}

}

void readin() {

	int L,now,A,B,Q,tmp;

	scanf("%d%d%d",&n,&K,&L);

	scanf("%d%d%d%d",&now,&A, &B, &Q);

	for (int i = 1; i < n; i++){

		now = (now * A + B) % Q; tmp = (i < L) ? i : L;

		build(i - now % tmp,i + 1);

	}

}

int main(){

	readin();

	dfs1(1);

	dfs2(1);

	work();

	return 0;

}