题意

Sunke 有一棵 $N + 1$ 个点的树,其中 $0$ 为根,每个点上有 $0$ 或 $1$ 个石子, Sunke 会不停的进行如下操作直至整棵树没有石子 :

把 $0$ 上面的石子从树上拿走放入口袋 ;
把每个点上的石子移到其父亲上 ;
对于每个点 , 若其石子数 $≥ 2$ , 则移除该点所有石子(不放入口袋)。

求对于所有 $2^{N+1}$ 种放置石子的方案 , 最终 Snuke 口袋中石子数是多少 , 对 $10^9+7$ 取模 .

$(1 \le N \le 2000) \ 400\mathrm{pts} \\ (1\le N \le 200000) \ 1000\mathrm{pts}.$

题解

$400\mathrm{pts}$

我们不难发现这个操作是层层独立的... 所以我们可以考虑隔离每层来算答案

考虑一层答案对于最终的贡献那么我们有一个显然的 $dp$

就是令 $dp[u][0/1]$ 为 $u$ 没/有石子的方案数 (已经考虑完了 $u$ 的子树)

我们不难发现我们只要考虑它儿子贡献出来的方案数

我们发现有多个石子一起合并上来的方案数不好算... 所以我们就可以用所有方案数减去贡献 $1$ 个的方案数

那么我们令 $All$ 为所有方案数 , 就有

\[\displaystyle All=\prod_{v \in G[u]} (dp[v][0]+dp[v][1])
\]

然后我们令 $Zero$ 为儿子全是 $0$ 的方案数 , 就有

\[\displaystyle Zero = \prod _{v \in G[u]} dp[v][0]
\]

然后又令 $One$ 为有一个儿子为 $1$ 的方案数 , 就有

\[\displaystyle One = \sum_{v \in G[u]} \frac{Zero \times dp[v][1]}{dp[v][0]}
\]

那我们就可以轻易更新当前的答案了

\[dp[u][0]=All-One \\ dp[u][1]=One
\]

然后每次考虑了一层后 (一开始我们只初始化了当层的答案)

我们最后要把 $dp[0][1]$ 乘上别的层数的方案数也就是 $2^{n + 1- tot[dep]}$ 然后加起来就是答案了..(代码见文末)

那么 $400\mathrm{pts}$ 就到手了qwq

然后我们考虑一下如何优化

有一个经常使用的套路那么就是启发式合并了...

我们把儿子 $dp$ 状态最多继承上来然后其他的状态暴力合并上去

把别的 $dp$ 状态暴力合并上来就行了

为了方便转移和空间问题我们每个点要动态开空间

就是我们每个点开个 vector<pair<long long, long long> >

它的下标从大到小表示当前点向下的深度从小到大

first 代表原来的 [0] ; second 代表原来的 [1] .

然后转移的时候下标就有些细节要注意一下

然后分析一波时间复杂度qwq

其实是 $O(n)$ 的 , 因为两个状态只会在其 $\mathrm{LCA}$ 上合并,然后同一层两两点的 $\mathrm{LCA}$ 只会有该层点数 $−1$ 个。

但我需要求一个逆元时间复杂度就变成 $O(n \log n) $ 了.... 但还是速度还行 (267ms)

那个如果用前缀积和后缀积的话就可以优化成 $O(n)$ 了但是不想写了...

代码

$400\mathrm{pts}$

#include <bits/stdc++.h>

#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)

#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)

#define Set(a, v) memset(a, v, sizeof(a))

using namespace std;

inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}

inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}

inline int read() {

    int x = 0, fh = 1; char ch = getchar();

    for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;

    for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);

    return x * fh;

}

void File() {

#ifdef zjp_shadow

	freopen ("E.in", "r", stdin);

	freopen ("E.out", "w", stdout);

#endif

}

typedef long long ll;

const ll Mod = 1e9 + 7;

const int N = 2010;

ll dp[N][2], ans = 0;

ll fpm(ll x, ll power) {

	ll res = 1;

	for (; power; power >>= 1, (x *= x) %= Mod)

		if (power & 1) (res *= x) %= Mod;

	return res;

}

int fa[N], n, dep[N], tot[N];

vector<int> G[N];

int main () {

	File();

	n = read();

	For (i, 1, n) {

		fa[i] = read();

		dep[i] = dep[fa[i]] + 1;

		G[fa[i]].push_back(i);

		++ tot[dep[i]];

	}

	++ tot[0];

	For (d, 0, n) {

		Fordown(i, n, 0) {

			if (dep[i] > d) continue ;

			if (dep[i] == d) {

				dp[i][0] = dp[i][1] = 1;

				continue ;

			}

			ll All = 1, Zero = 1;

			for (int v : G[i]) {

				(All *= (dp[v][0] + dp[v][1]) % Mod) %= Mod;

				(Zero *= dp[v][0]) %= Mod;

			}

			ll One = 0;

			for (int v : G[i])

				(One += Zero * fpm(dp[v][0], Mod - 2) % Mod * dp[v][1] % Mod) %= Mod;

			dp[i][0] = ((All - One) % Mod + Mod) % Mod;

			dp[i][1] = One;

		}

		(ans += dp[0][1] * fpm(2, n + 1 - tot[d]) % Mod) %= Mod;

	}

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

    return 0;

}

$1000\mathrm{pts}$

#include <bits/stdc++.h>

#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)

#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)

#define Set(a, v) memset(a, v, sizeof(a))

using namespace std;

inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}

inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}

inline int read() {

    int x = 0, fh = 1; char ch = getchar();

    for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;

    for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);

    return x * fh;

}

void File() {

#ifdef zjp_shadow

	freopen ("E.in", "r", stdin);

	freopen ("E.out", "w", stdout);

#endif

}

typedef long long ll;

typedef pair<ll, ll> pll;

#define fir first

#define sec second

#define mp make_pair

const ll Mod = 1e9 + 7;

const int N = 201000;

ll ans = 0;

ll fpm(ll x, ll power) {

	ll res = 1;

	for (; power; power >>= 1, (x *= x) %= Mod)

		if (power & 1) (res *= x) %= Mod;

	return res;

}

int fa[N], n, tot[N];

vector<int> G[N];

int id[N], num = 0, d[N];

vector<pll> dp[N];

ll All[N], Zero[N], One[N];

void Dfs(int u) {

	int son = n + 1;

	for (int v : G[u]) { Dfs(v); if (d[v] > d[son]) son = v;}

	if (son != n + 1) id[u] = id[son], d[u] = d[son] + 1;

	else id[u] = ++num;

	dp[id[u]].push_back(mp(1, 1));

	if ((int)G[u].size() == 1) return ;

	For (i, 0, d[u] - 1)

		All[i] = 1, Zero[i] = 1, One[i] = 0;

	int nowdep;

	for (int v : G[u])

		For (i, 0, d[v]) {

			nowdep = (d[son] - d[v]) + i;

			pll sta = dp[id[v]][i];

			(All[nowdep] *= (sta.fir + sta.sec)) %= Mod;

			(Zero[nowdep] *= sta.fir) %= Mod;

		}

	for (int v : G[u])

		For (i, 0, d[v]) {

			nowdep = (d[son] - d[v]) + i;

			pll sta = dp[id[v]][i];

			(One[nowdep] += Zero[nowdep] * fpm(sta.fir, Mod - 2) % Mod * sta.sec % Mod) %= Mod;

		}

	For (i, 0, d[u] - 1) {

		dp[id[u]][i].fir = (All[i] - One[i] + Mod) % Mod;

		dp[id[u]][i].sec = One[i];

	}

}

int dep[N];

int main () {

	File();

	n = read();

	For (i, 1, n) {

		fa[i] = read();

		G[fa[i]].push_back(i);

		dep[i] = dep[fa[i]] + 1;

		++ tot[dep[i]];

	}

	++ tot[0];

	d[n + 1] = -1;

	Dfs(0);

	For (i, 0, d[0]) {

		pll sta = dp[id[0]][i];

		(ans += sta.sec * fpm(2, n + 1 - tot[d[0] - i]) % Mod) %= Mod;

	}

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

	return 0;

}

巴特西

ARC 086 E - Smuggling Marbles(dp + 启发式合并)

题意

题解

代码

最新文章

热门文章