Original question: [Tsinghua training 2012] string beads

Enhanced version: Beaded enhanced version

The basic idea of this problem is the same as that of the problem solution written before Bombing program It can be seen that this is a common routine.

It is found that most of them are based on the shape pressure dp + enumeration subset, with time complexity \ (O(3^n) \).

Here is a \ (O (n ^ 2 ^ n) \) method. The measured data can pass through \ (n < = 20 \) within 2s. At present, it ranks first in the whole station.

Pre knowledge: fast Mobius transform, subset convolution

The previous push formulas are similar, but let's talk about it here.

The first step is to push the formula

We define:

\(f_S \) represents the number of schemes in which the set of \ (S \) constitutes a connected graph;

\(g_S \) represents the total scheme of random connection of \ (S \) sets (i.e. connection is not guaranteed).

We find \ (g \) by recursion:

Where \ (S' \) is obtained by removing any element \ (p \) from \ (S \), and "\ (+ 1 \)" can be disconnected.

It is difficult to find the connected scheme \ (f \) directly, but we consider calculating the unconnected scheme and then reduce it with the total scheme.

For the disconnected scheme, as long as the graph has more than two connected blocks, the graph is not connected. We seize this feature and consider enumerating one of the connected blocks, and the other points are left to live and die. As long as we don't connect the connected blocks enumerated to us, we can connect them casually, such a graph must be disconnected.

However, direct enumeration may be repeated, that is, when we enumerate one connected block \ (T \), and then enumerate another connected block \ (T '\), the \ (T \) appears in those points of self birth and death, which will obviously repeat the calculation.

As long as the connected blocks we enumerate successively always have intersection, they will not be counted as heavy. Consider extracting a point \ (p \) from \ (S \), and all connected blocks enumerated contain \ (p \), so the above situation will not occur. Like the previous formula, \ (S' \) is obtained by removing any element \ (p \) from \ (S \):

Here, the minus sign is convenient to replace the complement symbol. You can understand it.

To do this, you can already use the \ (O(3^n) \) enumeration subset. Next, I will make some changes to the formula to achieve better complexity.

The second step is a little transformation

Looking at this formula, does it look like subset convolution? Then let's make it more convolutive.

Note that \ (T \) in the original formula cannot take \ (S' \), so we move the item and merge:

In fact, the formula has been changed (true · a little change), but in order to find the answer, let's change the definition of \ (p \).

\(p \) can be any element in \ (S \), so we decide that \ (p \) is the highest element in \ (S \), that is \ (p=highbit(S) \).

Set the total number of points as \ (n \), and consider \ (S \) taking all \ ([2^{n-1},2^n-1] \), then \ (p=2^{n-1} \), \ (S'\in [0,2^{n-1}-1] \).

Looking back at our formula, we find that the first half of \ (g \) is convoluted with the subset of the second half of \ (f \) and becomes the second half of \ (g \).

Here, let \ (G_0 \) be the first half of \ (g \), and \ (G_1 \) be the second half. The same is true for \ (f \):

Where \ (* \) is subset convolution, and the division sign is its inverse operation.

And \ (g \) is known, and the answer is \ (f {2 ^ n-1} \) in the second half of \ (f \), so I finished the problem in \ (O (n ^ 2 ^ n) \).

Incidentally, the inverse of subset convolution is directly divided by polynomial for \ (g_0 \), \ (g_1 \) FMT, and finally IFMT. Because the number of items is very small, only \ (n \), violence can be divided.

Code:

#include<bits/stdc++.h>
#define R register int
#define ll long long
#define I inline
using namespace std;
const int N=20,M=1<<N,P=1e9+7;
int n,l,c[N][N],g[M],pc[M];//pc is popcount, the number of 1 in binary
I void pls(int &a,int b){a+=b;if(a>=P)a-=P;}
I void mns(int &a,int b){a-=b;if(a<0)a+=P;}
struct poly
{
	int a[N];
	void operator/=(const poly &p)
	{
		for(R i=1;i<=n;i++)
		{
			for(R j=0;j<i;j++)
				a[i]=(a[i]-1ll*a[j]*p.a[i-j])%P;
			if(a[i]<0)a[i]+=P;
		}
	}
	void operator+=(const poly &p){for(R i=0;i<=n;i++)pls(a[i],p.a[i]);}
	void operator-=(const poly &p){for(R i=0;i<=n;i++)mns(a[i],p.a[i]);}
};
poly g0[M>>1],g1[M>>1];
void FMT(poly *s)
{
	for(R i=1;i<l;i<<=1)
		for(R j=0;j<l;j+=i<<1)
			for(R k=j;k<j+i;k++)
				s[k+i]+=s[k];
}
void IFMT(poly *s)
{
	for(R i=1;i<l;i<<=1)
		for(R j=0;j<l;j+=i<<1)
			for(R k=j;k<j+i;k++)
				s[k+i]-=s[k];
}
int main()
{
	int rn,rl;
	scanf("%d",&rn);n=rn-1;//g. F. length treatment of split into two parts
	l=1<<n;rl=1<<rn;
	for(R i=0;i<rn;i++)
		for(R j=0;j<rn;j++)
			scanf("%d",c[i]+j);
	g[0]=1;
	for(R i=1,j,k;i<rl;i++)
	{
		for(j=0;!(i>>j&1);j++);
		g[i]=g[i&i-1];
		for(k=j+1;i>>k;k++)
			if(i>>k&1)g[i]=g[i]*(c[j][k]+1ll)%P;
	}
	pc[0]=-1;//The figure here is convenient to set the initial value to - 1, but in fact, it will become 0 later
	for(R i=0;i<l;i++)
	{
		pc[i]=pc[i&i-1]+1;
		g0[i].a[pc[i]]=g[i];
		g1[i].a[pc[i]]=g[i|l];
		//Note the processing of the occupation polynomial here. Since g is divided into two segments, the popcount in the latter half should be the original - 1
	}
	FMT(g0);FMT(g1);
	for(R i=0;i<l;i++)g1[i]/=g0[i];
	IFMT(g1);
	printf("%d",g1[l-1].a[n]);
	return 0;
}