[ZJOI2019]开关

以下的方案数默认是带权方案数。设\(P=\sum_{i=1}^np_i\)。

设\(F(x)\)为按\(i\)次开关后到达终止态的方案数的EGF，\(f\)为\(F\)的OGF，显然\(F(x)=\prod_{i=1}^n\frac{e^{\frac{p_ix}{P}}+(-1)^{s_i}e^{\frac{-p_ix}{P}}}{2}\)。初步的想法就是用\(f'(1)\)计算答案，但是这样是错误的，因为可能存在一些操作序列多次到达过终止态，这样就被重复计算了。设\(h(x)\)为按\(i\)次开关后第一次到达终止态的方案数的OGF，那么答案应该是\(h'(1)\)。

考虑怎样计算\(h\)。可以发现，\(f_i\)等于枚举一个前缀，使得进行完这个前缀的操作后第一次到达终止态，再进行剩下的操作回到这个原状态的方案数之和。设\(G\)为\(i\)次操作后回到原状态的方案数的EGF，\(g\)为\(G\)的OGF，显然\(G(x)=\prod_{i=1}^n\frac{e^{\frac{p_ix}{P}}+e^{\frac{-p_ix}{P}}}{2}\)。如果我们能求出\(f\)和\(g\)，那么\(gh=f,h=\frac{f}{g}\)。

考虑将\(F\)表示为\(\sum_{i=-P}^Pa_ie^{\frac{ix}{p}}\)的形式，把\(e\)拆开，每一项乘上对应的阶乘，可以得到\(f=\frac{a_i}{1-\frac{ix}{p}}\)。\(G\)同理。考虑怎样求\(h'(1)\)，用公式\((\frac{f}{g})'=\frac{f'g+g'f}{g^2}\)计算答案。但是把\(x=1\)代入\(f,g\)不收敛，所以把\(f,g\)同时乘上\(\prod_{i=-P}^P(1-\frac{ix}{p})\)。

剩下就是推式子的事了。

#include <bits/stdc++.h>

using namespace std;

const int N = 5e4 + 10;

const int mod = 998244353;

const int inv2 = (mod + 1) >> 1;

#define ms(a) memset(a,0,sizeof(a))

#define mc(a,b) memcpy(a,b,sizeof(a))

int n, s[N], p = 0, f[N << 1], g[N << 1], h[N << 1];

void inc(int &a, int b) {

  a += b;

  if(a >= mod) {

    a -= mod;

  }

}

int qpow(int a, int b) {

  int ret = 1;

  while(b) {

    if(b & 1) {

      ret = 1ll * ret * a % mod;

    }

    a = 1ll * a * a % mod, b >>= 1;

  }

  return ret;

}

int main() {

#ifndef ONLINE_JUDGE

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

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

#endif

  scanf("%d", &n);

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

    scanf("%d", s + i);

  }

  f[N] = g[N] = 1;

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

    scanf("%d", &x);

    for(int j = -p; j <= p; j++) {

      inc(h[j + x + N], 1ll * f[j + N]*inv2 % mod), inc(h[j - x + N], 1ll * f[j + N]*inv2 % mod * (s[i] ? mod - 1 : 1) % mod);

    }

    mc(f, h);

    ms(h);

    for(int j = -p; j <= p; j++) {

      inc(h[j + x + N], 1ll * g[j + N]*inv2 % mod), inc(h[j - x + N], 1ll * g[j + N]*inv2 % mod);

    }

    mc(g, h);

    ms(h);

    p += x;

  }

  int ans = 0;

  for(int i = -p; i < p; i++) {

    inc(ans, 1ll * (g[i + N] - f[i + N] + mod)*qpow(p - i, mod - 2) % mod);

  }

  cout << 1ll * ans*p % mod*qpow(2, n) % mod;

  return 0;

}

巴特西

[ZJOI2019]开关

最新文章

热门文章