P6295-有标号 DAG 计数【多项式求逆,多项式ln】
2024-09-01 15:55:46
正题
题目链接:https://www.luogu.com.cn/problem/P6295
题目大意
求所有\(n\)个点的弱联通\(DAG\)数量。
\(1\leq n\leq 10^5\)
解题思路
先不考虑弱联通的限制,求\(n\)个点的\(DAG\)数量。
设为\(f_i\),那么有式子
\[f_n=\sum_{i=1}^{n}\binom{n}{i}2^{i(n-i)}f_{n-i}(-1)^{i+1}
\]
\]
这个式子的意思是说新建一层出度为\(0\)的点,\(\binom{n}{i}\)很显然,然后\(2^{i(n-i)}\)是连边,然后\(f_{n-i}\)表示前面的方案。之后会发现这样的连法其实不保证原来出度为\(0\)的点现在都不为\(0\)了,也就是说这个是至少有\(i\)个出度为\(0\)的点的方案,那么要有一个容斥系数\((-1)^{i+1}\)。
然后把\(2^{i(n-i)}\)拆成\(2^{\binom{n}{2}}2^{-\binom{i}{2}}2^{-\binom{n-i}{2}}\)化一下两边的式子就是
\[\frac{f_n}{2^{\binom{n}{2}}n!}=\sum_{i=1}^n\frac{(-1)^{i+1}}{2^{\binom{i}{2}}i!}\frac{f_{n-i}}{2^{\binom{n-i}{2}}(n-i)!}
\]
\]
很经典的式子,设\(G(x)[n]=\frac{f_n}{2^{\binom{n}{2}}n!},F(x)[n]=\frac{(-1)^{n+1}}{2^{\binom{n}{2}}n!}\)
那么有
\[G=GF+1\Rightarrow G=\frac{1}{1-F}
\]
\]
多项式求逆就可以得到\(G\)。
然后得出数组\(f\),要求弱联通的话挺显然的就是如果弱联通的生成函数是\(H\),没有要求的是\(F\)
那么有
\[e^H=F\Rightarrow H=\ln(F)
\]
\]
所以在再个多项式ln就好了。
时间复杂度:\(O(n\log n)\)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=1<<17,M=N*8,P=998244353;
ll T,F[M],G[M],tmp[M],t1[M],t2[M],r[M];
ll power(ll x,ll b){
ll ans=1;
while(b){
if(b&1)ans=ans*x%P;
x=x*x%P;b>>=1;
}
return ans;
}
void NTT(ll *f,ll n,ll op){
for(ll i=0;i<n;i++)
if(i<r[i])swap(f[i],f[r[i]]);
for(ll p=2;p<=n;p<<=1){
ll len=p>>1,tmp=power(3,(P-1)/p);
if(op==-1)tmp=power(tmp,P-2);
for(ll k=0;k<n;k+=p){
ll buf=1;
for(ll i=k;i<k+len;i++){
ll tt=buf*f[i+len]%P;
f[i+len]=(f[i]-tt+P)%P;
f[i]=(f[i]+tt)%P;
buf=buf*tmp%P;
}
}
}
if(op==-1){
ll invn=power(n,P-2);
for(ll i=0;i<n;i++)
f[i]=f[i]*invn%P;
}
return;
}
void GetInv(ll *f,ll *g,ll n){
if(n==1){g[0]=power(f[0],P-2);return;}
GetInv(f,g,n>>1);ll m=n<<1;
for(ll i=0;i<n;i++)tmp[i]=F[i];
for(ll i=n;i<m;i++)tmp[i]=0;
for(ll i=0;i<m;i++)r[i]=(r[i>>1]>>1)|((i&1)?(m>>1):0);
NTT(tmp,m,1);NTT(g,m,1);
for(ll i=0;i<m;i++)g[i]=(2*g[i]-tmp[i]*g[i]%P*g[i]%P+P)%P;
NTT(g,m,-1);
for(ll i=n;i<m;i++)g[i]=0;
return;
}
void GetD(ll *f,ll *g,ll n){
for(ll i=0;i<n-1;i++)
g[i]=f[i+1]*(i+1)%P;
g[n-1]=0;return;
}
void GetJ(ll *f,ll *g,ll n){
for(ll i=1;i<n;i++)
g[i]=f[i-1]*power(i,P-2)%P;
g[0]=0;return;
}
void GetLn(ll *f,ll *g,ll n){
memset(t1,0,sizeof(t1));
memset(t2,0,sizeof(t2));
// n<<=1;
GetD(f,t1,n);
GetInv(f,t2,n);
ll m=n<<1;
for(ll i=0;i<m;i++)r[i]=(r[i>>1]>>1)|((i&1)?(m>>1):0);
NTT(t1,m,1);NTT(t2,m,1);
for(ll i=0;i<m;i++)t1[i]=t1[i]*t2[i]%P;
NTT(t1,m,-1);
for(ll i=n;i<m;i++)t1[i]=0;
GetJ(t1,g,n);return;
}
signed main()
{
F[1]=1;
for(ll i=2;i<N;i++)F[i]=P-F[P%i]*(P/i)%P;
F[0]=1;
for(ll i=1;i<N;i++)F[i]=F[i-1]*F[i]%P;
for(ll i=0;i<N;i++)F[i]=F[i]*power(power(2,i*(i-1)/2%(P-1)),P-2)%P;
for(ll i=0;i<N;i++)F[i]=(i&1)?(P-F[i]):F[i];
GetInv(F,G,N);
for(ll i=0;i<N;i++)F[i]=G[i]*power(2,i*(i-1)/2%(P-1))%P;
memset(G,0,sizeof(G));
GetLn(F,G,N);
scanf("%lld",&T);
for(ll i=1,pw=1;i<=T;i++,pw=pw*i%P)
printf("%lld\n",G[i]*pw%P);
return 0;
}
最新文章
- mysql优化笔记之分页
- wcf第3步之报文分析及原生调用
- (转)TortoiseGit(乌龟git)保存用户名密码的方法
- IIS32位,64位模式下切换
- Remove WebCakeDesktop
- JAVA基础知识之JVM-——使用反射生成并操作对象
- mysqldump备份数据库时排除某些库
- linux/win7下安装websphere application server
- Day 2 @ RSA Conference Asia Pacific & Japan 2016
- C++ Primer 学习笔记_54_类和数据抽象 --拷贝构造函数、赋值运算符
- MVVM With ReactiveCocoa让移动开发更简单
- CSS3中三角形及三角形组合图实现
- 【ASP】response和sever对象实现用户登录
- mysql 设置允许重试,批量更新
- 理解java的三大特性之封装
- jmeter 控制线程组执行顺序
- iOS webview注入JS
- js包管理工具-- yarn
- 使用Intent在活动之间穿梭
- javaweb(二十四)——jsp传统标签开发
热门文章
- 使用nmap命令扫描开放端口
- 踩坑记录之 -- String.IndexOf 在 .Net5 和 .Netcore3 中返回值不一样
- asp.net core 常见知识点
- 【mysql】单表使用索引常见的索引失效
- 玩转Spring生命周期之Lifecycle
- opencv入门系列教学(五)图像的基本操作(像素值、属性、ROI和边框)
- django1.9和mysql
- 笔记本+ubuntu18.04 关闭触摸板touchpad
- Cookie及通过Cookie常见应用
- 手把手教你在 SuperEdge 上用 EdgeX Foundry 接入 IoT 设备