제목.

제목의 대의.

N, N개의 점의 간단한 무방향도를 구하는 방안 수(번호 있음).그 결과 1004535809 1004535809 1004535809에 대해 모형을 뽑았다.

사고 과정

이 문제는 매우 고전적인 것 같다.그때는 한 무더기의 스타일이 떠올랐지만 무겁고 빠질 것 같아 버렸어요... 결국 더 이상 순수할 수 없을 정도로 폭력을 휘둘러 현지에서 O3를 켜고 111부터 88, 8까지 답을 모두 뛰어나와 시계를 그렸는데...

정해

정해의 일부분을 내가 놓친 것 같다.분명히 DP, fi f 설정ifi는 크기가 ii인 연통도 개수를 나타낸다. gigigi는 크기가 ii인 모든 그림의 개수를 나타낸다.분명히 g i = 2 C n 2 gi=2^{C n^2}gi=2Cn2 다음은 이동: 전체 상황으로 연결되지 않는 상황을 줄인다.연결되지 않는 상황에 대해 우리는 iii를 고정시키고 ii는 크기가 jjj인 연결 블록 안에 있고 나머지 i-3-ji-ji-3은 임의의 방식으로 배열하지만 ii가 있는 연결 블록과 연결되지 않는다.요약하면 fi = g i -3 ∑ j = 1 i -3 1 C i -3 1 j -3 1 f j i -3 j fi=g_i-\sum_{j=1}^{i-1}C_{i-1}^{j-1}f_jg_{i-j} fi=gi - ∑ j=1i - 1 Ci - 1 Ci - 1 j - 1 fj gi - j - 왜 안 무겁고 왜 안 빠지지?직감은 나에게 이것은 감성적으로 이해하는 물건이라고 말해 주었다.... 말로 묘사하기가 쉽지 않다. 다음에 식을 바꾸어 보자. f i = g i - (i - 1)!∑ j = 1 i − 1 f j ( j − 1 ) ! g i − j ( i − j ) ! f_i=g_i-(i-1)!\sum_{j=1}^{i-1}\frac{f_j}{(j-1)!}\frac{g_{i-j}}{(i-j)!} fi​=gi​−(i−1)!∑j=1i−1​(j−1)!fj​​(i−j)!gi -3 j 설정 F i = f i (i -3 1)!  G i = g i i ! F_i=\frac{f_i}{(i-1)!}\G_i=\frac{g_i}{i!} Fi​=(i−1)!fi​​ Gi​=i!gi​​, H i = ∑ j = 1 i − 1 F j G i − j H_i=\sum_{j=1}^{i-1}F_jG_{i-j}Hi=∑j=1i-3-1FjGi-3-j 우리는 이것이 권적의 형식이라는 것을 발견했다!그 다음은 하나의 분치 FFT(NTT)...(물론 나는 할 줄 몰랐지만) 사실 사상도 비교적 간단하다. 바로 CDQ로 분치하는 사상, 왼쪽의 물건으로 오른쪽에 대한 공헌을 계산하는 것이다.구체적으로 말하면 [l, m i d] [l, mid] [l, mid] [l, mid] [l, mid] [l, mid] [l, mid] [l, mid] [l, mid, mid] [l, mid] [m i d + 1, r] [m i d + 1, r] [mid+1, r] [mid+1, r] [mid+1, r] [mid+1, r] [mid+1, r] [mid] [mid+ 1, r] [m, r] [m i d, r] [m i d + 1,r] [m, r] [m i d + 1,r] [F 6, r] [m, r] [F i, r] [F l, r] [m, r] [m, r--l).위치의 대응 관계에 주의하세요.물론, 이 문제는 NTT를 사용하는 것이 당연히 더 좋다.FFT에 무서운 정밀도 문제가 있으니까... 1004535809 1004535809 1004535809는 NTT의 모델이고 원근은 333이다.n n 회 단위 뿌리를 뽑을 때 바로 3 m o - 1 n m o d & Thin Space;   mo 3^\rac {mo-1} {n}\mod mo 3nmo --1 modmo면 됩니다.NTT와 FFT는 거의 똑같아요. 구체적인 이론 부분은 섭렵하기 귀찮을 것 같아요.

코드

내가 말한 거랑 좀 다를 수도 있어.분치하기 전에 222의 멱을 잡았는데... 난용이 없는 것 같아...

using namespace std;
#include 
#include 
#include 
#include 
#define PI 3.14159263538979
#define mo 1004535809
#define N 131073
long long my_pow(long long x,long long y){
	long long res=1;
	for (;y;y>>=1,x=x*x%mo)
		if (y&1)
			res=res*x%mo;
	return res;
}
int n,m;
long long fac[N],inv[N];
long long f[N],g[N],h[N];
int M;
long long a[N*4],b[N*4],c[N*4];
int rev[N*4];
inline void ntt(long long*a,int flag){
	for (int i=0;i<M;++i)
		if (i<rev[i])
			swap(a[i],a[rev[i]]);
	for (int i=1;i<M;i<<=1){
		long long wn=my_pow(3,(mo-1)/(i*2));
		if (flag==-1)
			wn=my_pow(wn,mo-2);
		for (int j=0;j<M;j+=i<<1){
			long long wnk=1;
			for (int k=j;k<j+i;++k,wnk=wnk*wn%mo){
				long long x=a[k],y=wnk*a[k+i]%mo;
				a[k]=(x+y)%mo;
				a[k+i]=(x-y+mo)%mo;
			}
		}
	}
	long long invM=my_pow(M,mo-2);
	if (flag==-1)
		for (int i=0;i<M;++i)
			a[i]=a[i]*invM%mo;
}
inline void calc(){
	for (int i=0;i<M;++i){
		int tmp=0;
		for (int j=i,k=0;1<<k<M;j>>=1,++k)
			tmp=tmp<<1|j&1;
		rev[i]=tmp;
	}
	ntt(a,1),ntt(b,1);
	for (int i=0;i<M;++i)
		c[i]=a[i]*b[i];
	ntt(c,-1);
}
void dfs(int l,int r){
	if (l==r){
		f[l]=(g[l]-h[l]%mo*fac[l-1]%mo+mo)%mo;
		return;
	}
	int mid=l+r>>1;
	dfs(l,mid);
	for (M=1;M<=3*(mid-l);M<<=1);
	memset(a,0,sizeof(long long)*M);
	memset(b,0,sizeof(long long)*M);
	for (int i=0;i<mid-l+1;++i)
		a[i]=f[l+i]*inv[l+i-1]%mo;
	for (int i=0;i<mid-l+mid-l+1;++i)
		b[i]=g[i+1]*inv[i+1]%mo;
	calc();
	for (int i=mid-l;i<mid-l+mid-l+1;++i)
		h[l+i+1]+=c[i];
	dfs(mid+1,r);
}
int main(){
	scanf("%d",&n);
	fac[0]=1,inv[0]=1;
	for (int i=1;i<=n;++i)
		fac[i]=fac[i-1]*i%mo,inv[i]=my_pow(fac[i],mo-2);
	for (int i=1;i<=n;++i)
		g[i]=my_pow(2,1ll*i*(i-1)>>1);
	for (m=1;m<n;m*=2);
	dfs(1,m);
	printf("%lld
",f[n]);
	return 0;
}

총결산

DP 능력은 강화해야죠...