我是靠谱客的博主 瘦瘦宝马,这篇文章主要介绍GDOI2018 小学生图论题 [NTT],现在分享给大家,希望可以做个参考。

并没有传送门qwq


思路

首先要知道一个结论(或者说是一个套路):一个竞赛图缩点之后必定是一条链。

那么强联通分量的个数,就是这条链的边数+1。

考虑一条边什么时候会出现:当且仅当点集可以被分成(S,T)两个集合且他们之间的边全都是(Srightarrow T)的。

那么(m=0)时可以枚举点集大小,那么答案就是
[ 1+sum_{i=1}^{n-1} {nchoose i} (frac 1 2)^{i(n-i)} ]
(m>0)时仍然考虑枚举点集大小,此时每条链上的点要么全都在一边,要么被分成了两半,相当于做了个背包,可以用NTT优化。

但分成两半时中间的那条边已经固定了下来,没有必要算上它的(frac 1 2)

考虑把这个(frac 1 2)抵消掉,那么可以把它的系数置为2。

也就是说,对于一个(k)个点的链,它的多项式是(1+2x+2x^2+cdots+2x^{k-1}+x^k)

最后把所有链都乘起来变成(A(x)),那么答案就是
[ 1+sum_{i=1}^{n-1}{nchoose i}[x^i]A(x) ]


代码

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include<bits/stdc++.h> clock_t t=clock(); namespace my_std{ using namespace std; #define pii pair<int,int> #define fir first #define sec second #define MP make_pair #define rep(i,x,y) for (int i=(x);i<=(y);i++) #define drep(i,x,y) for (int i=(x);i>=(y);i--) #define go(x) for (int i=head[x];i;i=edge[i].nxt) #define templ template<typename T> #define sz 401010 #define mod 998244353ll typedef long long ll; typedef double db; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); templ inline T rnd(T l,T r) {return uniform_int_distribution<T>(l,r)(rng);} templ inline bool chkmax(T &x,T y){return x<y?x=y,1:0;} templ inline bool chkmin(T &x,T y){return x>y?x=y,1:0;} templ inline void read(T& t) { t=0;char f=0,ch=getchar();double d=0.1; while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar(); while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar(); if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();} t=(f?-t:t); } template<typename T,typename... Args>inline void read(T& t,Args&... args){read(t); read(args...);} char __sr[1<<21],__z[20];int __C=-1,__zz=0; inline void Ot(){fwrite(__sr,1,__C+1,stdout),__C=-1;} inline void print(register int x) { if(__C>1<<20)Ot();if(x<0)__sr[++__C]='-',x=-x; while(__z[++__zz]=x%10+48,x/=10); while(__sr[++__C]=__z[__zz],--__zz);__sr[++__C]='n'; } void file() { #ifndef ONLINE_JUDGE freopen("a.in","r",stdin); #endif } inline void chktime() { #ifndef ONLINE_JUDGE cout<<(clock()-t)/1000.0<<'n'; #endif } #ifdef mod ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;return ret;} ll inv(ll x){return ksm(x,mod-2);} #else ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x) if (y&1) ret=ret*x;return ret;} #endif // inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;} } using namespace my_std; int n,_m,m; int cc[sz]; ll _tmp[sz]; ll *a[sz]; int r[sz],limit; void NTT_init(int n) { int l=-1;limit=1; for (;limit<=n;limit<<=1) ++l; rep(i,0,limit-1) r[i]=(r[i>>1]>>1)|((i&1)<<l); } void NTT(ll *a,int type) { rep(i,0,limit-1) if (i<r[i]) swap(a[i],a[r[i]]); for (int mid=1;mid<limit;mid<<=1) { ll Wn=ksm(3,(mod-1)/mid>>1);if (type==-1) Wn=inv(Wn); for (int len=mid<<1,j=0;j<limit;j+=len) { ll w=1; for (int k=0;k<mid;k++,w=w*Wn%mod) { ll x=a[j+k],y=w*a[j+k+mid]%mod; a[j+k]=(x+y)%mod;a[j+k+mid]=(x-y+mod)%mod; } } } if (type==1) return; ll I=inv(limit); rep(i,0,limit-1) a[i]=a[i]*I%mod; } ll tmp[60][sz],len[60]; int st[60],top; int NTT(int l,int r) { if (l==r) { int ret=st[top--]; rep(i,0,cc[l]) tmp[ret][i]=a[l][i]; len[ret]=cc[l]; return ret; } int mid=(l+r)>>1; int L=NTT(l,mid),R=NTT(mid+1,r); int cur=st[top--]; NTT_init(len[L]+len[R]+2); NTT(tmp[L],1);NTT(tmp[R],1); rep(i,0,limit-1) tmp[cur][i]=tmp[L][i]*tmp[R][i]%mod; NTT(tmp[cur],-1); len[cur]=len[L]+len[R]; rep(i,0,limit-1) tmp[L][i]=tmp[R][i]=0; st[++top]=L;st[++top]=R; return cur; } int main() { file(); read(n,_m); int m=n,cur=0; rep(i,1,_m) { read(cc[i]); m-=cc[i]-1; rep(j,1,cc[i]) read(cc[0]); } rep(i,_m+1,m) cc[i]=1; rep(i,1,m) { a[i]=_tmp+cur; a[i][0]=a[i][cc[i]]=1; rep(j,1,cc[i]-1) a[i][j]=2; cur+=cc[i]+1; } rep(i,1,50) st[i]=i; top=50; int p=NTT(1,m); ll ans=1; rep(i,1,n-1) (ans+=tmp[p][i]*inv(ksm(2,1ll*i*(n-i)%(mod-1)))%mod)%=mod; cout<<ans; return 0; }

转载于:https://www.cnblogs.com/p-b-p-b/p/10819878.html

最后

以上就是瘦瘦宝马最近收集整理的关于GDOI2018 小学生图论题 [NTT]的全部内容,更多相关GDOI2018内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(165)

评论列表共有 0 条评论

立即
投稿
返回
顶部