[ZJOI2019]开关

本文主要是介绍[ZJOI2019]开关，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

难难。

知:
\(e^x = \sum \frac{x^i}{i!}\)
\(e^{-x} = \sum (-1)^i\frac{x^i}{i!}\)

那么知设\(i\)步后达到目标的概率\(EGF\)为 \(f_e(x)\)

有\(f_e(x) = \prod \frac{e^{p_ix} + (-1)^{s_i}e^{-p_ix}}{2}\)

设第\(i\)步恰好回到目标的\(EGF\)为\(g_e(x)\)

\(g_e(x) = \prod \frac{e^{p_ix} + e^{-p_ix}}{2}\)

考虑对其转为\(OGF\)，为\(f,g\)。

那么知第一次打到目标的\(OGF\)有\(hg = f\),答案即为\((\frac{f}{g})'(1)\)

知\((\frac{f(x)}{g(x)})' = \frac{f'(x)g(x) - g'(x)f(x)}{g^2(x)}\)

设 \(\phi_{1 - k} = [x^k]\prod(x^{p_i} + (-1)^{s_i}x^{-p_i}\)

考虑继续推导：

\(=[x^{\sum p_i - k}]\prod(1 + (-1)^{s_i}x^{2p_i}),\sum p_i = 1\)

所以\(\phi_{1 - k} = [x^{1 - k}](1 + (-1)^{s_i}x^{2p_i})\)

同理定义 \(\gamma_i\)

根据 \(EGF\) 转 \(OGF\) 知：

\(h(x) = \frac{\sum\frac{\phi_{1 - i}}{2^n}\frac{1}{1 - ix}}{\sum\frac{\gamma_{1 - i}}{2^n}\frac{1}{1 - ix}} =\frac{\phi_0 + \sum_{i \neq 1}\phi_{1 - i}\frac{1-x}{1-ix}}{\gamma_0 + \sum_{i \neq 1}\gamma_{1 - i}\frac{1-x}{1-ix}}\)

左边转右边的主要目的，我们最终需要带入\(x = 1\)的值，而左边不能如此，我们最终右边同乘一个\((1 - x)\)

考虑对其直接求导，带入特殊点值，知\(h'(1) = \sum_{i > 0}{\frac{\gamma_i - \phi_i}{i}}\)

对其进行 \(n\)个体积\(2p_i\) 的背包即可

//晦暗的宇宙，我们找不到光，看不见尽头，但我们永远都不会被黑色打倒。——Quinn葵因
#include<bits/stdc++.h>
#define ll long long
#define N 500050
#define mod 998244353

int n,m;

int b[N];

int inv[N];

ll ans;

ll f[N],g[N];

int main(){
	scanf("%d",&n);
	for(int i = 1;i <= n;++i)
	scanf("%d",&b[i]);
	f[0] = g[0] = inv[1] = 1;
	for(int i = 1;i <= n;++i){
		int x;
		scanf("%d",&x);
		int j;
		for(j = m,m += x;~j;--j){
			(f[j + x] += b[i] ? mod - f[j] : f[j]) %= mod;
			(g[j + x] += g[j]) %= mod;
		}
	}
	for(int i = 2;i <= m;++i)
	inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
	for(int i = 1;i <= m;++i)
	ans = (ans + 1ll * (g[i] - f[i] + mod) * inv[i] % mod * inv[2] % mod * m % mod) % mod;
	std::cout<<ans<<"\n";
}

这篇关于[ZJOI2019]开关的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！