2159: Crash 的文明世界

Description

Input

Output

Sample Input

Sample Output

HINT

恕我直言，我还是第一次见这么奇葩的题目描述

都告诉了输入格式，结果最后给你来一团像乱码一样的东西告诉你这才是真正的输入格式...

就这，我re了两次.... 辣鸡题面，降我ac率(掀桌

看到i^k这种格式，以及该题性质，会想到第二类斯特林数.

即

其中表示第二类斯特林数.

第二类斯特林数表示把i个数分成j个无序集合的个数.

那么

因为单考虑第i个数，可以把这个数分别放入前j-1个集合有j-1种方案，还可以单独一个集合 1种方案

而c是可以递推的，令f[i][j]表示在第i个点disi为j的和

那么对于一个点x，他所能到达更远的所有点一定是能到他的距离+ 1 那么可以直接用组合数算出来

那么考虑从叶子节点向上递推可以算出根节点f值。

然后再从根节点向下推，此时要注意原本从某个点转移过来的方案数.

另外因为有减法，还要 + p再 % p

c++代码如下：

#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i = x; i <= y;++ i)
#define repd(i,x,y) for(register int i = x; i >= y;-- i)
using namespace std;
typedef long long ll;
template<typename T>inline void read(T&x)
{x = 0;char c;int sign = 1;do { c = getchar(); if(c == '-') sign = -1; }while(!isdigit(c));do { x = x * 10 + c - '0'; c = getchar(); }while(isdigit(c));x *= sign;
}const int p = 1e4+7,N = 5e4+500,K = 155;
int s[K][K],f[N][K],ans[N],out[N],fa[N],F[K],t[K],n,k;
int head[N],nxt[N<<1],to[N<<1],tot;inline void add(int x,int y)
{to[tot] = y;nxt[tot] = head[x];head[x] = tot++;
}void dfs(int x)
{for(register int i = head[x];~i;i = nxt[i])if(to[i] != fa[x]){fa[to[i]] = x;out[x] ++;dfs(to[i]);}
}void Uncompress(FILE *infile, FILE *outfile)
{int N, k, L, i, now, A, B, Q, tmp;fscanf(infile, "%d%d%d", &N, &k, &L);fscanf(infile, "%d%d%d%d", &now, &A, &B, &Q);fprintf(outfile, "%d %d\n", N, k);for (i = 1; i < N; i ++){now = (now * A + B) % Q;tmp = (i < L) ? i : L;fprintf(outfile, "%d %d\n", i - now % tmp, i + 1);} 
}int main()
{memset(head,-1,sizeof head);int L,now,tmp,A,B,Q;read(n); read(k); read(L);read(now); read(A); read(B); read(Q); rep(i,1,n - 1){int u,v;now = (now * A + B) % Q;tmp = (i < L) ? i : L;u = i - now % tmp,v = i + 1;add(u,v); add(v,u);}dfs(1);F[1] = 1;rep(i,2,k) F[i] = 1LL*F[i - 1]*i%p;s[0][0] = 1;rep(i,1,k)rep(j,0,i)if(j) s[i][j] = (1LL*s[i - 1][j] * j % p + s[i - 1][j - 1]) % p; else s[i][j] = 1LL*s[i - 1][j] * j % p;queue<int>q;rep(i,1,n) if(!out[i]) q.push(i);while(!q.empty()){int x = q.front();q.pop();f[x][0]++;int y = fa[x];if(y){out[y] --;if(!out[y]) q.push(y); rep(i,0,k)if(i) f[y][i] = (f[y][i] + f[x][i - 1] + f[x][i]) % p;else f[y][i] = (f[y][i] + f[x][i])%p;}}q.push(1);while(!q.empty()){int x = q.front();q.pop();rep(i,1,k)ans[x] = (1LL*s[k][i] * F[i] % p * f[x][i] % p + ans[x])%p;for(register int i = head[x];~i;i = nxt[i])if(to[i] != fa[x]){rep(j,0,k)if(j == 0) t[j] = f[x][j];else if(j == 1) t[j] = ((f[to[i]][j] + f[x][j] + f[x][j - 1] - (f[to[i]][j] + f[to[i]][j - 1]) - f[to[i]][j - 1])%p+p)%p;else t[j] = ((f[to[i]][j] + f[x][j] + f[x][j - 1] - (f[to[i]][j] + f[to[i]][j - 1]) - (f[to[i]][j - 1] + f[to[i]][j - 2]))%p + p)%p;memcpy(f[to[i]],t,sizeof t);q.push(to[i]);}}rep(i,1,n) printf("%d\n",ans[i]);return 0;
}