脚本宝典收集整理的这篇文章主要介绍了[省选集训2022] 模拟赛20，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
题目描述
给定一个 (ntimes m) 的网格图，边有边权，初始边权都是 (0)，有 (q) 次修改，每次修改一条边的边权，问修改后网格图的最小生成树是多少，强制在线。
(ntimes MLeq 10^5,qleq 2cdot 10^5)
解法
重点在于考察网格图的性质，不难发现总边数是 ((n-1)m+n(m-1))，而最小生成树上的边数是 (nm-1)，那么没有出现在最小生成树上的边数量是 (nm-n-m+1)，如果你数感比较好，想到网格图的对偶图点数是 (nm-n-m+2)，就能发现，网格图最小生成树的补集对应着对偶图的最大生成树。
那么我们同时维护最小生成树和最大生成树，修改就分类讨论：
用 (tt lct) 即可实现支持动态插入的最小生成树，@R_971_1304@ (O(qLOG nm))，不想写代码了。
题目描述
点 (iin[1,n]) 可以向 (p_iin[0,n]) 连边，对应的权值是 (w_{i-j+nbmod n})；特别地，如果 (p_i=0) 对应的权值是 (1)，定义生成树的权值为边的权值乘积，问所有可能的生成树权值和。
(nleq 2^{20})
解法
显然题目是求以 (0) 为根的内向生成树的权值和，应用矩阵树定理，我们想要求出下列矩阵的行列式，设 (s=sum w_i)：
那么就是一个对循环矩阵求行列式的问题，考虑公式：
其中 (f(x)=sum_{i=0}^{n-1} a_icdot x^i)，那么可以一次 (tt NTT) 计算出来，时间复杂度 (O(nlog n))
#include <cstdio>
#include <iostream>
using namespace std;
const int M = 1<<20;
#define int long long
const int MOD = 998244353;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,ans,p[M],f[M],rev[M];
int qkpow(int a,int b)
{
int r=1;
while(b>0)
{
if(b&1) r=r*a%MOD;
a=a*a%MOD;
b>>=1;
}
return r;
}
void NTT(int *a,int len,int op)
{
for(int i=0;i<len;i++)
{
rev[i]=(rev[i>>1]>>1)|((i&1)*(len/2));
if(i<rev[i]) swap(a[i],a[rev[i]]);
}
for(int s=2;s<=len;s<<=1)
{
int w=(op==1)?qkpow(3,(MOD-1)/s):
qkpow(3,MOD-1-(MOD-1)/s);
for(int i=0,t=s/2;i<len;i+=s)
for(int j=0,x=1;j<t;j++,x=x*w%MOD)
{
int fe=a[i+j],fo=a[i+j+t];
a[i+j]=(fe+x*fo)%MOD;
a[i+j+t]=(fe-x*fo%MOD+MOD)%MOD;
}
}
if(op==1) return ;
int inv=qkpow(len,MOD-2);
for(int i=0;i<len;i++)
a[i]=a[i]*inv%MOD;
}
signed main()
{
freoPEn("federation.in","r",stdin);
freopen("federation.out","w",stdout);
n=1<<read();
for(int i=1;i<n;i++) p[0]+=p[i]=read();
f[0]=(p[0]+1)%MOD;
for(int i=1;i<n;i++) f[i]=(MOD-p[i])%MOD;
NTT(f,n,1);ans=1;
for(int i=0;i<n;i++) ans=ans*f[i]%MOD;
printf("%lldn",ans);
}
以上是脚本宝典为你收集整理的[省选集训2022] 模拟赛20全部内容，希望文章能够帮你解决[省选集训2022] 模拟赛20所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。