bzoj_2159 Crash 的文明世界

题目:

  Crash 小朋友最近迷上了一款游戏——文明5 (Civilization V)。在这个游戏中,玩家可以建立和发展自己的国家,通过外交和别的国家交流,或是通过战争征服别的国家。
  现在 Crash 已经拥有了一个个城市的国家,这些城市之间通过道路相连。由于建设道路是有花费的,因此 Crash 只修建了条道路连接这些城市,不过可以保证任意两个城市都有路径相通。
  在游戏中,Crash 需要选择一个城市作为他的国家的首都,选择首都需要考虑很多指标,有一个指标是这样的:
  其中表示第个城市的指标值,表示第个城市到第个城市需要经过的道路条数的最小值,为一个常数且为正整数。
  因此 Crash 交给你一个简单的任务:给出城市之间的道路,对于每个城市,输出这个城市的指标值,由于指标值可能会很大,所以你只需要输出这个数的值。

思路:

  一开始的想法是把用点分治把一条路径长度表示成 ,然后幂次用二项式展开。这样就有了一个 的做法。
  首先有一个这样的式子:
  从放球模型的角度来解释这个式子,左边是 种球任意摆放在 个位置的方案数,右边先把 个位置分成 组,每组选择一种球放。不难发现左右是相等的。
  那么 点对应的答案就是
  把与 有关的项拎出来:
  然后可以考虑 求后面那个 ,因为 是每次变大 的,所以可以利用 转移。设 表示 子树中表达式的值,那么转移就是
  最后只要用换根 优化枚举根的过程即可。

代码:

#include <bits/stdc++.h>
#define File(_) freopen(#_ ".in", "r", stdin), freopen(#_ ".out", "w", stdout)
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define mcpy(a, b) memcpy(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++)
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

bool cur1;

const int N = 50005, MOD = 10007;

template<int N, int M, class T> struct Link {
#define erep(k, G, o) for(int k(G.HEAD[o]); k; k = G.NXT[k])
    int HEAD[N], NXT[M], tot; T W[M];
    void add(int x, T w) {NXT[++tot] = HEAD[x]; W[HEAD[x] = tot] = w;}
    T& operator[] (int k) {return W[k];}
};
Link<N, N * 2, int> G;

int dp[N][155], m;
void dfs1(int o, int f) {
    dp[o][0] = 1;
    erep(k, G, o) {
        int v = G[k];
        if(v == f) continue;
        dfs1(v, o);
        (dp[o][0] += dp[v][0]) %= MOD;
        rep(i, 1, m) (dp[o][i] += dp[v][i] + dp[v][i - 1]) %= MOD;
    }
}
int tmp[N];
void dfs2(int o, int f) {
    erep(k, G, o) {
        int v = G[k];
        if(v == f) continue;
        mcpy(tmp, dp[o]);
        (tmp[0] -= dp[v][0]) %= MOD;
        rep(i, 1, m) (tmp[i] -= dp[v][i] + dp[v][i - 1]) %= MOD;
        dp[v][0] += tmp[0];
        rep(i, 1, m) (dp[v][i] += tmp[i] + tmp[i - 1]) %= MOD;
        dfs2(v, o);
    }
}

int strn[155][155], fac[155];
void init(int m) {
    fac[0] = 1;
    rep(i, 1, m) fac[i] = (ll) fac[i - 1] * i % MOD;
    strn[0][0] = 1;
    rep(i, 1, m) rep(j, 1, i) 
        strn[i][j] = (strn[i - 1][j - 1] + j * strn[i - 1][j]) % MOD;
}

int main() {
    File(civilization);
    int n;
    scanf("%d%d", &n, &m);
    init(m);
    int tmp, x, y, A, B, Q, now, L;
    scanf("%d%d%d%d%d", &L, &now, &A, &B, &Q);
    rep(i, 1, n - 1) {
        now = (now * A + B) % Q, tmp = i < L ? i : L;
        x = i - now % tmp, y = i + 1;
        G.add(x, y); G.add(y, x);
    }
    dfs1(1, 0); dfs2(1, 0);
    rep(o, 1, n) {
        int ans = 0;
        rep(i, 0, m) 
            (ans += strn[m][i] * fac[i] % MOD * dp[o][i] % MOD) %= MOD;
        printf("%d\n", (ans + MOD) % MOD);
    }
    return 0;
}