IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> C++知识库 -> 2022牛客多校#4 C. Easy Counting Problem -> 正文阅读

[C++知识库]2022牛客多校#4 C. Easy Counting Problem

C. Easy Counting Problem

题目大意

定义好字符串,满足:

  • 包含十进制下小于 w ( 2 ≤ w ≤ 10 ) w(2 \leq w \leq 10) w(2w10) 的数字
  • 数字 i i i 至少出现 c i ( 1 ≤ c i ≤ 50000 , ∑ c i ≤ 50000 ) c_i(1 \leq c_i \leq 50000,\sum c_i \leq 50000) ci?(1ci?50000,ci?50000)

q ( 1 ≤ q ≤ 300 ) q(1 \leq q \leq 300) q(1q300) 次询问,每次询问求解有多少个不同的长度为 n ( 1 ≤ n ≤ 1 0 7 ) n(1 \leq n \leq 10^7) n(1n107) 的好字符串。

题解

考虑生成函数,由于求排列计数,因此考虑EGF。
数字 k k k 至少出现 c k c_k ck? 次,其对应的EGF为
f k ( x ) = x c k c k ! + x c k + 1 ( c k + 1 ) ! + x c k + 2 ( c k + 2 ) ! + . . . = e x ? ∑ i = 0 c k ? 1 x i i ! \begin{aligned} f_k(x)&=\frac{x^{c_k}}{c_k!}+\frac{x^{c_k+1}}{(c_k+1)!}+\frac{x^{c_k+2}}{(c_k+2)!}+...\\ &=e^x-\sum_{i=0}^{c_k-1}{\frac{x^i}{i!}} \end{aligned} fk?(x)?=ck?!xck??+(ck?+1)!xck?+1?+(ck?+2)!xck?+2?+...=ex?i=0ck??1?i!xi??

所有条件汇总的EGF为
F ( x ) = ∏ k = 0 w ? 1 f k ( x ) = ∏ k = 0 w ? 1 ( e x ? ∑ i = 0 c k ? 1 x i i ! ) F(x)=\prod_{k=0}^{w-1}{f_k(x)}=\prod_{k=0}^{w-1}(e^x-\sum_{i=0}^{c_k-1}{\frac{x^i}{i!}}) F(x)=k=0w?1?fk?(x)=k=0w?1?(ex?i=0ck??1?i!xi?)

对于每个询问的 n n n F ( x ) F(x) F(x) [ x n n ! ] [\frac{x^n}{n!}] [n!xn?] 的系数即为答案。
a n s n = [ x n n ! ] ∏ k = 0 w ? 1 ( e x ? ∑ i = 0 c k ? 1 x i i ! ) ans_n=[\frac{x^n}{n!}]\prod_{k=0}^{w-1}(e^x-\sum_{i=0}^{c_k-1}{\frac{x^i}{i!}}) ansn?=[n!xn?]k=0w?1?(ex?i=0ck??1?i!xi?)

上式无法直接卷积,考虑单独提出 e x e^x ex
F ( x ) = ∑ i = 0 w ? 1 e i x ? ( ? 1 ) w ? 1 ? i ? g w ? 1 , w ? 1 ? i ( x ) F(x)=\sum_{i=0}^{w-1}e^{ix}\cdot (-1)^{w-1-i} \cdot g_{w-1,w-1-i}(x) F(x)=i=0w?1?eix?(?1)w?1?i?gw?1,w?1?i?(x)

其中 g i , j g_{i,j} gi,j? 表示在 { ∑ k = 0 c i ? 1 x k k ! } \{\sum_{k=0}^{c_i-1}{\frac{x^k}{k!}}\} {k=0ci??1?k!xk?} 的前 i i i 项中,选取了 j j j 项之积的表达式之和。存在转移式
g i , j = g i ? 1 , j + g i ? 1 , j ? 1 ? ∑ k = 0 c i ? 1 x k k ! g_{i,j}=g_{i-1,j}+g_{i-1,j-1}\cdot \sum_{k=0}^{c_i-1}{\frac{x^k}{k!}} gi,j?=gi?1,j?+gi?1,j?1??k=0ci??1?k!xk?

可以采用NTT在 O ( w 2 C log ? C ) O(w^2C\log C) O(w2ClogC) 的复杂度内(其中 C = ∑ c i C=\sum c_i C=ci?),求解出所有的 g i , j ( x ) g_{i,j}(x) gi,j?(x) ,并且其最高次不超过 C C C

考虑拆开 e i x = ∑ j = 0 + ∞ i j j ! x j e^{ix}=\sum_{j=0}^{+\infty}{\frac{i^j}{j!}x^j} eix=j=0+?j!ij?xj
F ( x ) = ∑ i = 0 w ? 1 ( ? 1 ) w ? 1 ? i ? g w ? 1 , w ? 1 ? i ( x ) ∑ j = 0 + ∞ i j j ! x j = ∑ i = 0 w ? 1 h i ( x ) ∑ j = 0 + ∞ i j j ! x j \begin{aligned} F(x)&=\sum_{i=0}^{w-1}(-1)^{w-1-i} \cdot g_{w-1,w-1-i}(x)\sum_{j=0}^{+\infty}{\frac{i^j}{j!}x^j}\\ &=\sum_{i=0}^{w-1}h_i(x)\sum_{j=0}^{+\infty}{\frac{i^j}{j!}x^j} \end{aligned} F(x)?=i=0w?1?(?1)w?1?i?gw?1,w?1?i?(x)j=0+?j!ij?xj=i=0w?1?hi?(x)j=0+?j!ij?xj?

求解上式中 [ x n n ! ] [\frac{x^n}{n!}] [n!xn?] 的系数,由于最高次 C = ∑ c i ≤ 50000 C=\sum c_i\leq 50000 C=ci?50000 ,依次可以枚举 h i ( x ) h_i(x) hi?(x) 中第 k k k x k x^k xk 的系数 [ x k ] h i ( x ) [x^k]h_i(x) [xk]hi?(x) ,则还需在 ∑ j = 0 + ∞ i j j ! x j \sum_{j=0}^{+\infty}{\frac{i^j}{j!}x^j} j=0+?j!ij?xj 中选取 n ? k n-k n?k 项的系数,即 i n ? j ( n ? j ) ! \frac{i^{n-j}}{(n-j)!} (n?j)!in?j?

因此答案为
a n s n = n ! ? ∑ i = 0 w ? 1 ∑ k = 0 n i n ? j ( n ? j ) ! [ x k ] h i ( x ) ans_n=n!\cdot\sum_{i=0}^{w-1}\sum_{k=0}^n{\frac{i^{n-j}}{(n-j)!}[x^k]h_i(x)} ansn?=n!?i=0w?1?k=0n?(n?j)!in?j?[xk]hi?(x)

其中 n ! n! n! 用于将 x n x^n xn 的系数转化为 [ x n n ! ] [\frac{x^n}{n!}] [n!xn?] 的系数。

参考代码

来自SolitaryDrea

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
#define DOR(i,s,t) for(int i=(s),_t=(t); i>=_t; --i)
typedef long long ll;
const int Mod=998244353;
const int N=2e5+50;
const int M=1e7+50;
bool __;

ll Fast(ll x,int b) {
	ll t=1;
	for(; b; b>>=1,x=x*x%Mod) {
		if(b&1) t=t*x%Mod;
	}
	return t;
}
void DFT(ll *a,int n,int f) {
	static int rev[N],ww[N],iw[N],pn=0;
	if(pn!=n) {
		ll p=Fast(3,(Mod-1)/n);
		ww[0]=1;
		FOR(i,1,n-1) ww[i]=ww[i-1]*p%Mod;
		iw[n-1]=Fast(ww[n-1],Mod-2);
		DOR(i,n-1,1) iw[i-1]=iw[i]*p%Mod;
		FOR(i,0,n-1) rev[i]=(rev[i>>1]>>1)|((i&1)*(n>>1));
		pn=n;
	}
	int *w=(f>0)?ww:iw;
	FOR(i,0,n-1) if(rev[i]<i) swap(a[rev[i]],a[i]);
	for(int l=2; l<=n; l<<=1) {
		for(ll *p=a; p!=a+n; p+=l) {
			for(int i=0,m=l>>1; i<m; ++i) {
				ll t=p[i+m];
				p[i+m]=(p[i]+w[n/l*(i+m)]*t)%Mod;
				p[i]=(p[i]+w[n/l*i]*t)%Mod;
			}
		}
	}
	if(f<0) {
		ll t=Fast(n,Mod-2);
		FOR(i,0,n-1) a[i]=a[i]*t%Mod;
	}
}
void Poly_Mul(const ll *A,int LenA,const ll *B,int LenB,ll *C) {
	static ll a[N],b[N];
	int n=1;for(; n<LenA+LenB; n<<=1);
	FOR(i,0,n-1) a[i]=b[i]=0;
	FOR(i,0,LenA-1) a[i]=A[i];
	FOR(i,0,LenB-1) b[i]=B[i];
	DFT(a,n,1);DFT(b,n,1);
	FOR(i,0,n-1) C[i]=a[i]*b[i]%Mod;
	DFT(C,n,-1);
}

ll Fac[M],Inv[M];
ll a[12][N];
ll b[N],g[N];
ll C(int n,int m) {
	return Fac[n]*Inv[n-m]%Mod*Inv[m]%Mod;
}
bool ___;
int main() {
	int n=1e7;
	Fac[0]=1;
	FOR(i,1,n) Fac[i]=Fac[i-1]*i%Mod;
	Inv[n]=Fast(Fac[n],Mod-2);
	DOR(i,n,1) Inv[i-1]=Inv[i]*i%Mod;
	int w;
	scanf("%d",&w);
	a[0][0]=1;
	int K=0;
	FOR(i,1,w) {
		int c;
		scanf("%d",&c);
		FOR(i,0,c-1) b[i]=-Inv[i];
		DOR(j,i-1,0) {
			Poly_Mul(a[j],K+1,b,c,g);
			FOR(k,0,K+c-1) a[j+1][k]=(a[j+1][k]+g[k])%Mod;
		}
		
		K+=c-1;
	}
	int q;
	scanf("%d",&q);
	while(q--) {
		scanf("%d",&n);
		ll res=0;
		FOR(i,0,w) {
			ll u=Fast(w-i,n);
			ll v=Fast(w-i,Mod-2);
			FOR(j,0,min(K,n)) {
				if(w-i) {
					res=(res+Fac[n]*a[i][j]%Mod*Inv[n-j]%Mod*u)%Mod;
					u=u*v%Mod;
				} else if(n-j==0) {
					res=(res+Fac[n]*a[i][j]%Mod*Inv[n-j]%Mod)%Mod;
				}
			}
		}
		if(res<0) res+=Mod;
		printf("%lld\n",res);
	}
	return 0;
}
  C++知识库 最新文章
【C++】友元、嵌套类、异常、RTTI、类型转换
通讯录的思路与实现(C语言)
C++PrimerPlus 第七章 函数-C++的编程模块(
Problem C: 算法9-9~9-12:平衡二叉树的基本
MSVC C++ UTF-8编程
C++进阶 多态原理
简单string类c++实现
我的年度总结
【C语言】以深厚地基筑伟岸高楼-基础篇(六
c语言常见错误合集
上一篇文章      下一篇文章      查看所有文章
加:2022-08-06 10:25:04  更:2022-08-06 10:29:00 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年3日历 -2024/3/29 8:01:01-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码