首页 > 其他分享 >[CF755G] PolandBall and Many Other Balls 题解

[CF755G] PolandBall and Many Other Balls 题解

时间：2023-02-27 23:12:10浏览次数：55  
标签：Balls frac int 题解 CF755G sqrt ++ len 6x

[CF755G] PolandBall and Many Other Balls 题解

题意概括

有一排 \(n\) 个球，定义一个组可以只包含一个球或者包含两个相邻的球。现在一个球只能分到一个组中，求从这些球中取出 \(k\) 组的方案数。

\(n\le 10^9\)，\(k<2^{15}\)。

题目分析

容易想到 \(dp\) 转移：设 \(f_{i,j}\) 表示考虑前 \(i\) 个球，取了 \(j\) 组的方案数，那么有转移 \(f_{i,j}=f_{i-1,j-1}+f_{i-1,j-2}+f_{i-1,j}\) ，暴力转移 \(O(nk)\) 。可以考虑多项式去优化，即令 \(F_i(x)=\sum_{j=0}^{k}f_{i,j}x^j\) ，则有：

\[F_i(x)=(1+x)\times F_{i-1}(x)+x\times F_{i-2} \]

这个式子显然可以构造其母函数 \(G(F(x))\) ，那么就有（下文记 \(t=F(x)\) ，为一个多项式）：

\[\begin{aligned} &G(t)=(1+x)\times t\times G(t)+x\times t^2 \times G(t)+1\\ &(1-(1+x)\times t-x\times t^2)G(t)=1\\ &G(t)=\frac{1}{1-(1+x)t-x\times t^2} \end{aligned} \]

然后就是套路地解这个生成函数即可，设：

\[\begin{aligned} G(t)&=\frac{\mu}{1-At}+\frac{\varphi}{1-Bt}\\ &=\frac{\mu-B\mu t+\varphi -A\varphi t}{1-(A+B)t+ABt^2} \end{aligned} \]

然后解方程组：

\[\left\{ \begin{matrix} \mu+\varphi=1\\ B\mu+A\varphi=0\\ A+B=1+x\\ AB=x \end{matrix} \right. \Rightarrow \left\{ \begin{matrix} \mu=\frac{1+x+\sqrt{1+6x+x^2}}{2\sqrt{1+6x+x^2}}\\ \varphi=\frac{\sqrt{1+6x+x^2}-1-x}{2\sqrt{1+6x+x^2}}\\ A=\frac{1+x+\sqrt{1+6x+x^2}}{2}\\ B=\frac{1+x-\sqrt{1+6x+x^2}}{2}\\ \end{matrix} \right. \]

所以说：

\[G(t)=\frac{(\frac{1+x+\sqrt{1+6x+x^2}}{2\sqrt{1+6x+x^2}})}{(1-\frac{1+x+\sqrt{1+6x+x^2}}{2})}+\frac{(\frac{\sqrt{1+6x+x^2}-1-x}{2\sqrt{1+6x+x^2}})}{(1-\frac{1+x-\sqrt{1+6x+x^2}}{2})} \]

然后就得到了 \(G(t)\) 的每一项的系数，也即 \(F(x)\) 的通项公式：

\[\begin{aligned} G_i(t)=F_i(x)&=\frac{1+x+\sqrt{1+6x+x^2}}{2\sqrt{1+6x+x^2}}\times (\frac{1+x+\sqrt{1+6x+x^2}}{2})^{i}+\frac{\sqrt{1+6x+x^2}-1-x}{2\sqrt{1+6x+x^2}}\times (\frac{1+x-\sqrt{1+6x+x^2}}{2})^{i}\\\\ &=\frac{1}{\sqrt{1+6x+x^2}}\times ((\frac{1+x+\sqrt{1+6x+x^2}}{2})^{i+1}-(\frac{1+x-\sqrt{1+6x+x^2}}{2})^{i+1})\\\\ \end{aligned} \]

由于 \(1+x-\sqrt{1+6x+x^2}\) 的常数项为 \(0\) ，所以说 \((\frac{1+x-\sqrt{1+6x+x^2}}{2})^{i+1}\) 的 \(x^0\) 到 \(x^{i+1}\) 项系数均为 \(0\) ，所以说式子可以进一步化简，变得十分优美 ：

\[F_n(x)=\frac{1}{\sqrt{1+6x+x^2}}\times(\frac{1+x+\sqrt{1+6x+x^2}}{2})^{i+1} \]

多项式快速幂就能解决（并且快速幂过程常数项一直为 \(1\) ，非常好写） ，下面附上代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 30;
const int M = 3e5;
const int mod = 998244353;
const int pr = 3;
const int ig = 332748118;

inline int add(int x, int y) {
	x += y;
	return x >= mod ? x - mod : x;
}

inline int del(int x, int y) {
	x -= y;
	return x < 0 ? x + mod : x;
}

int qpow(int a, int b) {
	int res = 1;
	while(b) {
		if(b & 1) res = 1ll * res * a % mod;
		a = 1ll * a * a % mod;
		b >>= 1;
	}
	return res;
}

struct node {
	int n, mx = 1, f[N], g[N];
	void NTT(int *a, int len) {
		int x, y, g, pw;
		for(int j = len >> 1; j >= 1; j >>= 1) {
			g = qpow(pr, (mod - 1) / (j << 1));
			for(int i = 0; i < len; i += (j << 1)) {
				pw = 1;
				for(int k = 0; k < j; ++k, pw = 1ll * pw * g % mod) {
					x = a[i + k]; y = a[i + j + k];
					a[i + k] = add(x, y);
					a[i + j + k] = 1ll * pw * del(x, y) % mod;
				}
			}
		}
	}
	
	void INTT(int *a, int len) {
		int x, y, g, pw;
		for(int j = 1; j < len; j <<= 1) {
			g = qpow(ig, (mod - 1) / (j << 1));
			for(int i = 0; i < len; i += (j << 1)) {
				pw = 1;
				for(int k = 0; k < j; ++k, pw = 1ll * pw * g % mod) {
					x = a[i + k]; y = 1ll * pw * a[i + j + k] % mod;
					a[i + k] = add(x, y);
					a[i + j + k] = del(x, y);
				}
			}
		}
		int Inv = qpow(len, mod - 2);
		for(int i = 0; i < len; ++i) a[i] = 1ll * a[i] * Inv % mod;
	}
	
	void mul(int *a, int *b, int len) {
		NTT(a, len); NTT(b, len);
		for(int i = 0; i < len; ++i) a[i] = 1ll * a[i] * b[i] % mod;
		INTT(a, len);
	}
	
	void INV(int *a, int *b, int len) {
		static int A[N], B[N];
		for(int i = 0; i < len; ++i) A[i] = a[i], a[i] = 0;
		for(int i = 0; i < len; ++i) B[i] = b[i], b[i] = 0;
		B[0] = qpow(A[0], mod - 2);
		for(int j = 2; j < len; j <<= 1) {
			for(int i = 0; i < (j << 1); ++i) a[i] = b[i] = 0;
			for(int i = 0; i < j; ++i) a[i] = A[i];
			for(int i = 0; i < (j >> 1); ++i) b[i] = B[i];
			mul(a, b, j << 1);
			for(int i = j; i < (j << 1); ++i) a[i] = 0;
			for(int i = 0; i < j; ++i) a[i] = (mod - a[i]) % mod;
			a[0] = add(a[0], 2);
			NTT(a, j << 1);
			for(int i = 0; i < (j << 1); ++i) a[i] = 1ll * a[i] * b[i] % mod;
			INTT(a, j << 1);
			for(int i = 0; i < j; ++i) B[i] = a[i];
		}
		for(int i = 0; i < len; ++i) a[i] = A[i], A[i] = 0;
		for(int i = 0; i < len; ++i) b[i] = B[i], B[i] = 0;
	}
	
	void LN(int *a, int *b, int len) {
		static int A[N], B[N];
		for(int i = 0; i < len; ++i) A[i] = a[i], a[i] = 0;
		for(int i = 0; i < len; ++i) B[i] = b[i], b[i] = 0;
		INV(A, B, len);
		for(int i = 0; i < len; ++i) b[i] = B[i];
		for(int i = 0; i < (len >> 1) - 1; ++i) a[i] = 1ll * A[i + 1] * (i + 1) % mod;
		for(int i = (len >> 1); i < len; ++i) a[i] = b[i] = 0;
		mul(a, b, len);
		for(int i = 1; i < (len >> 1); ++i) B[i] = 1ll * a[i - 1] * qpow(i, mod - 2) % mod;
		B[0] = 0;
		for(int i = 0; i < len; ++i) a[i] = A[i], A[i] = 0;
		for(int i = 0; i < len; ++i) b[i] = B[i], B[i] = 0;
	}
	
	void EXP(int *a, int *b, int len) {
		static int A[N], B[N];
		for(int i = 0; i < len; ++i) A[i] = a[i], a[i] = 0;
		for(int i = 0; i < len; ++i) B[i] = b[i], b[i] = 0;
		B[0] = 1;
		for(int j = 2; j < len; j <<= 1) {
			for(int i = 0; i < (j << 1); ++i) a[i] = b[i] = 0;
			for(int i = 0; i < j; ++i) a[i] = B[i];
			LN(a, b, j << 1);
			for(int i = j; i < (j << 1); ++i) b[i] = 0;
			for(int i = 0; i < j; ++i) b[i] = del(A[i], b[i]);
			b[0] = add(b[0], 1);
			mul(a, b, j << 1);
			for(int i = 0; i < j; ++i) B[i] = a[i];
			for(int i = j; i < (j << 1); ++i) B[i] = 0;
		}
		for(int i = 0; i < len; ++i) a[i] = A[i], A[i] = 0;
		for(int i = 0; i < len; ++i) b[i] = B[i], B[i] = 0;
	}

	void SQRT(int *a, int *b, int len) {
		static int A[N], B[N];
		for(int i = 0; i < len; ++i) A[i] = a[i], a[i] = 0;
		for(int i = 0; i < len; ++i) B[i] = b[i], b[i] = 0;
		B[0] = 1;
		for(int j = 2; j < len; j <<= 1) {
			for(int i = 0; i < (j << 1); ++i) a[i] = b[i] = 0;
			for(int i = 0; i < (j >> 1); ++i) a[i] = b[i] = B[i];
			mul(a, b, j);
			for(int i = 0; i < j; ++i) a[i] = (a[i] + A[i]) % mod;
			for(int i = 0; i < (j >> 1); ++i) b[i] = 2ll * B[i] % mod;
			for(int i = (j >> 1); i < j; ++i) b[i] = 0;
			INV(b, B, j << 1);
			for(int i = j; i < (j << 1); ++i) B[i] = 0;
			mul(a, B, j << 1);
			for(int i = 0; i < j; ++i) B[i] = a[i];
			for(int i = j; i < (j << 1); ++i) B[i] = 0;
		}
		for(int i = 0; i < len; ++i) a[i] = A[i];
		for(int i = 0; i < len; ++i) b[i] = B[i];
	}
	
	void QPOW(int *a, int *b, int len, int val) {
		LN(a, b, len);
		for(int i = 0; i < (len >> 1); ++i) b[i] = 1ll * b[i] * val % mod;
		EXP(b, a, len);
		for(int i = 0; i < (len >> 1); ++i) b[i] = a[i];
	}
	
	void init() {while(mx <= n + n) mx <<= 1;}
}F, G;

int n, k;

int main() {
	scanf("%d%d", &n, &k); int mem = k; k = min(k, n);
	G.n = F.n = k; F.init(); G.init();
	G.f[0] = 1; G.f[1] = 6; G.f[2] = 1;
	G.SQRT(G.f, G.g, G.mx);
	for(int i = 0; i < G.mx; ++i) G.f[i] = 0;
	for(int i = G.n + 1; i < G.mx; ++i) G.g[i] = 0;
	G.INV(G.g, G.f, G.mx);
	for(int i = 0; i < G.mx; ++i) F.f[i] = G.g[i];
	F.f[0] = add(F.f[0], 1); F.f[1] = add(F.f[1], 1);
	for(int i = 0; i < F.mx; ++i) F.f[i] = 1ll * F.f[i] * 499122177 % mod;
	F.QPOW(F.f, F.g, F.mx, n + 1);
	for(int i = F.n + 1; i < F.mx; ++i) F.f[i] = 0;
	F.mul(F.f, G.f, F.mx);
	for(int i = F.n + 1; i < F.mx; ++i) F.f[i] = 0;
	for(int i = 1; i <= mem; ++i) printf("%d ", F.f[i]);
	return 0;
}

\(END.\)

标签：Balls,frac,int,题解,CF755G,sqrt,++,len,6x
From： https://www.cnblogs.com/zyc070419-blog/p/17162322.html

相关文章

  • Django uwsgi问题解析
    通常情况下，部署Django应用到生产环境时都会通过uwsgi部署，uwsgi一些配置项配置问题有可能会导致服务出现502状态码或者其他超时等的情况常用到的配置项如下:reload-on-as......
  • 【题解】P3747 [六省联考 2017] 相逢是问候
    思维难度作为一道省选题还是有待商榷，但是代码确实挺恶心的。记一下这种有关无穷层幂嵌套（无穷幂塔）的套路。思路扩展欧拉定理+线段树。首先看到不断嵌套幂并且模数较大......
  • QFileDialog实现同时选择文件和文件夹，确认取消按钮英文问题解决方法
    如下图所示，需求是同时能够选择文件或者文件夹，但是QFileDialog文件窗口类要么只能选文件，要么只能选文件夹，无法同时去选择文件和文件夹； 要实现这样的需求，封装了一个类，实现......
  • 2021 联合省选 A 卷题解
    比2022小清新了许多。卡牌游戏首先可以知道的是按照\(a\)升序排序，肯定有一段区间的\(a\)全保留，然后剩下的全翻面。那么我们需要求出最长的这段区间是什么。首先......
  • AtCoder Beginner Contest 280 A-F 题解
    比赛链接A-PawnonaGrid模拟。#include<cstdio>#include<algorithm>#include<cstring>usingnamespacestd;constintN=15;intn,m,ans;chars[N];i......
  • AtCoder Beginner Contest 279 A-E 题解
    比赛链接A-wwwvvvvvv直接模拟#include<cstdio>#include<cstring>constintN=105;intn,ans;chars[N];intmain(){ scanf("%s",s+1); for(inti=1......
  • AtCoder Beginner Contest 291 A-F 题解
    。。。比赛链接A-camelCase直接循环判断。#include<cstdio>#include<cstring>constintN=20;chars[N];intmain(){ scanf("%s",s+1); for(inti=1;......
  • 题解：【ABC291F】Teleporter and Closed off
    题目链接给定一个\(n\)个点的图，每个点只向编号最多大于它\(m\)的点连单向边，求不经过\(2\simn\)中的一个点，\(1\ton\)的最短路。注意到\(m\)很小，这里给出两种......
  • 【Eclipse 问题】Eclipse老项目打包war后的WEB-INF目录下没有classes文件夹的问题解决
    1.右键项目Properties2.选中JavaBuildPath中的Source3.点击浏览4.在WEB-INF目录下新建一个classes文件夹，用来存放编译好的class文件。5.完成......
  • 【题解】CTT 2020 Day 1
    目录A.术树数B.树数术C.述树术A.术树数注意到路径+环的组合仍然可行，因为我们可以在无影响的情况下加入环（显然一条边也算二元环）。而对于每条边，如果其在某些环内，只要......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99