CF 848E（动态规划+分治NTT）

传送门：

http://codeforces.com/problemset/problem/848/E

题解：

假设0-n一定有一条边，我们得到了一个方案，那么显然是可以旋转得到其他方案的。

记最大的i满足i到i+n有一条边，那么旋转的方案数是n-i

考虑动态规划：

设\(g[i]\)表示i个点，只用相邻或隔一个去拼接的方案数。

转移显然有\(g[i]=g[i-2]+g[i-4]\)。

设\(f[i][0/1][0/1]\)表示1有连对面的，n+1有连对面的，2-n填，前面后面是否要伸出去的方案数。

那么显然有\(f[i][j][k]=g[i-1-j-k]*(i-1)^2\)。

设\(h[i][0/1]\)表示前i个确定了，第i个是连对面，后面是否伸出去。

显然有\(h[i][v]=\sum_{j=0}^{i-1}h[j][u]*f[i-j][u][v]\)

初值为：\(h[0][0]=1->ans+=?*h[?][0]\)

\(h[0][1]=1->ans+=?*h[?][1]\)

由于最后一段有长度的额外贡献，所以：

\(Ans=\sum_{i=0}^{n-1}h[i][u]*f[n-i][u][?]*(n-i)\)

这个东西显然可以分治NTT优化转移。

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()

namespace ntt {

	const int nm = 131072;

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

	void build() {

		for(int i = 1; i < nm; i *= 2) ff(j, 0, i)

			w[i + j] = ksm(3, (mo - 1) / 2 / i * j);

	}

	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;

		int n = 1; while(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 a, V b) {

	ntt :: fft(a, b);

	return a;

}

const int N = 50005;

int n;

ll f[N][2][2], g[N], h[N][2], ans;

void dp(int x, int y, int m, int u, int v) {

	V p, q;

	p.resize(m - x + 1);

	fo(i, x, m) p[i - x] = h[i][u];

	q.resize(y - x + 1);

	ff(i, 0, q.si) q[i] = f[i][u][v];

	p = p * q;

	fo(i, m + 1, y) h[i][v] = (h[i][v] + p[i - x]) % mo;

}

void dg(int x, int y) {

	if(x == y) return;

	int m = x + y >> 1;

	dg(x, m);

	fo(u, 0, 1) fo(v, 0, 1) dp(x, y, m, u, v);

	dg(m + 1, y);

}

int main() {

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

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

	ntt :: build();

	scanf("%d", &n);

	g[0] = 1;

	fo(i, 1, n) g[i] = ((i < 2 ? 0 : g[i - 2]) + (i < 4 ? 0 : g[i - 4])) % mo;

	fo(i, 1, n) fo(j, 0, 1) fo(k, 0, 1)

		f[i][j][k] = (i - 1 - j - k >= 0) ? g[i - 1 - j - k] * (i - 1) % mo * (i - 1) % mo: 0;

	h[0][0] = 1;

	dg(0, n - 1);

	fo(i, 0, n - 1) fo(v, 0, 1) ans = (ans + h[i][v] * f[n - i][v][0] % mo * (n - i)) % mo;

	memset(h, 0, sizeof h); h[0][1] = 1;

	dg(0, n - 1);

	fo(i, 0, n - 1) fo(v, 0, 1) ans = (ans + h[i][v] * f[n - i][v][1] % mo * (n - i)) % mo;

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

}

巴特西

CF 848E（动态规划+分治NTT）

传送门：

题解：

最新文章

热门文章