2019.07.05【NOIP提高組】模拟 A 組（分治NTT模闆、上下界網絡流）

T1：這題很簡單。

把所有邊按頻率排序，枚舉選邊的區間，然後用并查集維護加邊就可以了。

T2：這一題是一個複雜的上下界網絡流+動态加邊。

首先我們建立源點和彙點sd、td，然後從sd向所有i連流量限制為(0,inf)，費用為in[i]的邊（簡稱(0,inf,in[i])，下同）。然後從i向td連(0,inf,out[i])。這兩種邊表示i可以随時向sd或td流流量以減少或增加自身的流量，但是要話費in或out的費用。

如果i的left為負，那麼就i向td連(-left,-left,0)，否則sd向i連(left,left,0)。而對于原圖的一條邊(x,y,a,b,down,up)，我們就把它拆成a+b,3a+b,5a+b……那麼我們就能表示出所有流量的情況了。

對于這一個圖，跑一遍有上下界的費用流，跑出來的就是答案。

注意：實際上，一條x、y的最開始的邊不是a+b，而是以down為流量的費用。而且我們要在網絡流過程中不斷調整x、y的費用，防止出錯。因為我們是優先選a+b、再3a+b……以此類推。

至于有上下界的網絡流，參考我寫的“上下界網絡流”這篇部落格。

T3：首先我們要推出一個式子，設f[i]表示n=i時的答案，那麼f[i]=2^C(i,2)-sum(f[j]*C(i-1,j-1)*2^C(i-j,2))，(1<=j<=i-1)。

這條式子的意思就是用總的方案數-不合法的方案數。總的方案數就是2^C(i,2)。至于不合法的方案數我們就枚舉一個i的子點集，設大小為j，并且我們規定1号點在選出來的集合裡面（防止重複計算），那麼保證j大小的點集為聯通塊的方案數是f[j]，從i個點中選j個點并且要包含1号點的方案數為C(i-1,j-1)，最後剩下的i-j的點之間可以随便連邊（反正這已經是一個不聯通圖了），那麼我們就得出了上面這一條式子。

但計算這條式子的時間複雜度是n^2的。是以我們化簡一下：

f[i]=2^C(i,2)-sum(f[j]*C(i-1,j-1)*2^C(i-j,2))

=2^C(i,2)-sum(f[j]*(i-1)!/(j-1)!/(i-j)!*2^C(i-j,2))

然後把1/(j-i)!與f[j]放在一起，1/(i-j)!與2^C(i-j,2)放在一起，(i-1)!提出來，那麼原式就變成了

f[i]=2^(i,2)-(i-1)!*sum(f[j]/(j-1)!*2^C(i-j,2)/(i-j)!)。

設F[i]=f[i]/(i-1)!，G[i]=2^C(i,2)/i!，接着把上面式子同除(i-1)!，那麼就得到了

F[i]=2^(i,2)/(i-1)!-sum(F[j]*G[i-j])，這顯然就是一個卷積的形式。

我們的目的是求F（G是可以預處理出來的），但是我們又不能直接用NTT做，因為更新後面F要用到前面的F，是以我們考慮用分治NTT。

所謂的分治NTT就是每次計算l~mid的F對mid+1~r的貢獻。

注意：1、目前l~r的區間隻能用l~mid的F乘某些G去給mid+1~r的F貢獻。不在mid+1~r區間裡的F是不能被目前l~mid貢獻的。這樣做是為了防止重複計算。

2、“某些G”的具體範圍是1~r-l+1，因為F[x]*G[y]是對F[x+y]貢獻的，是以我們用l~mid的F去給mid+1~r做貢獻，G的取值範圍就是1~r-l+1。

下面貼一下代碼：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#define ll long long
#define MAXN 520010

ll a[MAXN],b[MAXN],F[MAXN],G[MAXN],jc[MAXN],sum[MAXN],rev[MAXN],mod=1004535809,bit,s,n,g=3,ans;
ll sqr(ll x,ll y)
{
	ll w=y,j=x%mod,s=1;
	while(w>=1)
	{
		if(w%2==1)s=(s*j)%mod;
		j=(j*j)%mod;
		w/=2;
	}
	return s;
}
int getrev()
{
	ll i;
	for(i=0;i<s;i++)rev[i]=((rev[i>>1]>>1)|((i&1)<<(bit-1)));
}
int NTT(ll *a,ll inv)
{
	ll i,j,step,k,x,y,wn,wnk,t;
	for(i=0;i<s;i++)
		if(i<rev[i]){t=a[i];a[i]=a[rev[i]];a[rev[i]]=t;}
	for(step=1;step<s;step*=2)
	{
		if(inv==1)wn=sqr(g,(mod-1)/(step*2));
		else wn=sqr(sqr(g,(mod-1)/(step*2)),mod-2);
		for(j=0;j<s;j=j+step*2)
		{
			wnk=1;
			for(k=j;k<j+step;k++)
			{
				x=a[k];y=wnk*a[k+step]%mod;
				a[k]=(x+y)%mod;a[k+step]=(x-y+mod)%mod;
				wnk=(wnk*wn)%mod;
			}
		}
	}
}
int work()
{
	ll i,v;
	getrev();
	NTT(a,1);NTT(b,1);
	for(i=0;i<s;i++)a[i]=a[i]*b[i]%mod;
	NTT(a,-1);
	v=sqr(s,mod-2);
	for(i=0;i<s;i++)a[i]=a[i]*v%mod;
}
int dg(ll l,ll r)
{
	ll i,mid=(l+r)/2,left,right;
	if(l==r)
	{
		if(l!=1)F[l]=(sqr((ll)2,l*(l-1)/2)*sqr(jc[l-1],mod-2)%mod-sum[l]+mod)%mod;
		else F[l]=1;
		return 0;
	}
	dg(l,mid);
	left=1;right=r-l+1;
	s=1;bit=0;
	while(s<right-left+1)s*=2,bit++;
	for(i=0;i<s;i++)a[i]=0,b[i]=0;
	for(i=l;i<=mid;i++)a[i-l]=F[i];
	for(i=left;i<=right;i++)b[i-left]=G[i];
	for(i=mid-l+1;i<s;i++)a[i]=0;
	for(i=right-left+1;i<s;i++)b[i]=0;
	work();
	for(i=0;i<s;i++)
		if(i+l+left>=mid+1&&i+l+left<=r)sum[i+l+left]=(sum[i+l+left]+a[i])%mod;
	dg(mid+1,r);
}
int main()
{
ll i,j;
scanf("%lld",&n);
ans=n;n=1;
while(n<ans)n*=2;
jc[0]=1;for(i=1;i<=n*2;i++)jc[i]=(jc[i-1]*i)%mod;
G[1]=1;
for(i=2;i<=n*2;i++)G[i]=sqr((ll)2,i*(i-1)/2)*sqr(jc[i],mod-2)%mod;
dg(1,n);
printf("%lld",F[ans]*jc[ans-1]%mod);
}