7.12模拟T2（套路容斥+多项式求逆）

Description：

\(n<=10,max(w)<=1e6\)

题解：

考虑暴力，相当于走多维格子图，不能走有些点。

套路就是设\(f[i]\)表示第一次走到i的方案数

\(f[i]=起点到点i的方案数-\sum_{j在i前面}f[j]*j到i的方案数\)

不妨把前缀和后缀的分开，设为f和g。

f上的点形如(i,i,…)

设\(m=min(w)\),\(w-=m\)

则g上的点形如(w+i,……)

这样就顺序了。

且\(i->j的方案数\)之和坐标差有关，那就可以分治NTT了。

还可以优化，设\(f->f的转移多项式是A,f->g是B，g->f是C\)

则有

\(F=A-F*A-G*C\)

\(G=B-G*A-F*B\)

最后答案就是\(G[m]\)

消元可得：

\(G={B \over (1+A)^2-BC}\)

所以求逆即可。

Code：

#include<bits/stdc++.h>

#define fo(i, x, y) for(int i = x, B = y; i <= B; i ++)

#define ff(i, x, y) for(int i = x, B = y; i <  B; i ++)

#define fd(i, x, y) for(int i = x, B = y; i >= B; i --)

#define ll long long

#define pp printf

#define hh pp("\n")

using namespace std;

const int mo = 998244353;

ll ksm(ll x, ll y) {

	ll s = 1;

	for(; y; y /= 2, x = x * x % mo)

		if(y & 1) s = s * x % mo;

	return s;

}

typedef vector<ll> V;

#define pb push_back

#define si size()

const int nm = 1 << 21;

namespace ntt {

	ll w[nm], a[nm], b[nm]; int r[nm];

	void build() {

		for(int i = 1; i < nm; i *= 2) {

			ll v = ksm(3, (mo - 1) / 2 / i);

			w[i] = 1; ff(j, 1, i) w[i + j] = w[i + j - 1] * v % mo;

		}

	}

    void dft(ll *a, int n, int f) {

        ff(i, 0, n) {

            r[i] = r[i / 2] / 2 + (i & 1) * (n / 2);

            if(i < r[i]) swap(a[i], a[r[i]]);

        } ll b;

        for(int i = 1; i < n; i *= 2) for(int j = 0; j < n; j += 2 * i)

            ff(k, 0, i) b = a[i + j + k] * w[i + k], a[i + j + k] = (a[j + k] - b) % mo, a[j + k] = (a[j + k] + b) % mo;

        if(f == -1) {

            reverse(a + 1, a + n);

            b = ksm(n, mo - 2);

            ff(i, 0, n) a[i] = (a[i] + mo) * b % mo;

        }

    }

	void fft(V &p, V &q) {

		int p0 = p.si + q.si - 1, n = 1;

		for(; n < p0; n *= 2);

		ff(i, 0, n) a[i] = b[i] = 0;

		ff(i, 0, p.si) a[i] = p[i];

		ff(i, 0, q.si) b[i] = q[i];

		dft(a, n, 1); dft(b, n, 1);

		ff(i, 0, n) a[i] = a[i] * b[i] % mo;

		dft(a, n, -1);

		p.resize(p0);

		ff(i, 0, p0) p[i] = a[i];

	}

}

V operator * (V p, V q) {

	ntt :: fft(p, q);

	return p;

}

void dft(V &p, int f) {

	ff(i, 0, p.si) ntt :: a[i] = p[i];

	ntt :: dft(ntt :: a, p.si, f);

	ff(i, 0, p.si) p[i] = ntt :: a[i];

}

V qni(V a) {

	int a0 = a.si, n0 = 1;

	while(n0 < a0) n0 *= 2;

	V b; b.resize(1); b[0] = ksm(a[0], mo - 2);

	for(int n = 2; n <= n0; n *= 2) {

		V d = b; d.resize(n); b.resize(2 * n);

		V c = a; c.resize(n); c.resize(2 * n);

		dft(c, 1); dft(b, 1);

		ff(i, 0, b.si) b[i] = c[i] * b[i] % mo * b[i] % mo;

		dft(b, -1); b.resize(n);

		ff(i, 0, b.si) b[i] = (2 * d[i] - b[i] + mo) % mo;

	}

	b.resize(a0);

	return b;

}

const int N = 1e7 + 5;

ll fac[N], nf[N];

V a, b, c;

void build(int n) {

	fac[0] = 1; fo(i, 1, n) fac[i] = fac[i - 1] * i % mo;

	nf[n] = ksm(fac[n], mo - 2); fd(i, n, 1) nf[i - 1] = nf[i] * i % mo;

}

int n, m, w[11];

void build2() {

	a.resize(m + 1); b.resize(m + 1); c.resize(m + 1);

	fo(i, 1, m) a[i] = fac[n * i] * ksm(nf[i], n) % mo;

	fo(i, 0, m) {

		int s = 0; b[i] = 1;

		fo(j, 1, n) s += w[j] + i, b[i] = b[i] * nf[w[j] + i] % mo;

		b[i] = b[i] * fac[s] % mo;

	}

	fo(i, 0, m) {

		int s = 0; c[i] = 1;

		fo(j, 1, n) {

			if(-w[j] + i < 0) c[i] = 0; else

			s += -w[j] + i, c[i] = c[i] * nf[-w[j] + i] % mo;

		}

		c[i] = c[i] * fac[s] % mo;

	}

}

ll f[N], g[N];

int main() {

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

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

	ntt :: build();

	scanf("%d", &n); m = 1e6;

	fo(i, 1, n) scanf("%d", &w[i]), m = min(m, w[i]);

	fo(i, 1, n) w[i] -= m;

	{

		int ye = 1;

		fo(i, 1, n) if(w[i]) ye = 0;

		if(ye) {

			pp("0\n"); return 0;

		}

	}

	build(1e7);

	build2();

	a[0] ++; a = a * a; a.resize(m + 1);

	c = c * b; c.resize(m + 1);

	ff(i, 0, a.si) a[i] = (a[i] - c[i] + mo) % mo;

	a = qni(a); b = b * a;

	pp("%lld\n", b[m]);

}

巴特西

7.12模拟T2（套路容斥+多项式求逆）

Description：

题解：

Code：

最新文章

热门文章