序列[2020聯考][dp]

文章目錄

• 題目
• 思路
• 代碼

題目

思路

可以發現對于一個素數最多 2 2 2 個數擁有

然後這兩個數連邊

發現向前隻有 1 1 1 條邊

那麼轉化成森林方案數

首先計算一棵樹的方案數

f i S : i 個 節 點 素 數 占 用 集 合 為 S 樹 的 方 案 數 f_{iS}: i 個節點素數占用集合為S樹的方案數 fiS​:i個節點素數占用集合為S樹的方案數

轉移要麼連邊要麼自己加

然後

g i S : i 個 節 點 素 數 占 用 集 合 為 S 森 林 的 方 案 數 g_{iS}: i個節點素數占用集合為S森林的方案數 giS​:i個節點素數占用集合為S森林的方案數

樹和樹之間是不同的，是以每次轉移欽定新加入樹的最後一個點在最後，排列組合即可

注意代碼實作

代碼

#include<set>
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<climits>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
LL read(){
	LL f=0,x=0;char c=getchar();
	while(c<'0'||'9'<c){if(c=='-')f=1;c=getchar();}
	while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return !f?x:-x;
}
#define mp make_pair
const int MAXN=(1<<6);
const int Mod=(int)(1e9+7);
int f[25][MAXN+5],h[MAXN+5],g[25][MAXN+5];
int m,a[10],C[30][30];
int bitcnt(int x){
	int cnt=0;
	while(x) cnt++,x-=(x&-x);
	return cnt;
}
int main(){
	freopen("seq.in","r",stdin);
	freopen("seq.out","w",stdout);
	LL n=read(),tt=n;
	for(int i=0;i<=25;i++)
		C[i][0]=C[i][i]=1;
	for(int i=1;i<=25;i++)
		for(int j=1;j<i;j++)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%Mod;
	for(LL i=2;i*i<=tt;i++)
		if(tt%i==0){
			m++;
			while(tt%i==0)
				a[m]++,tt/=i;
		}
	if(tt!=1)
		a[++m]=1;
	for(int s=0;s<(1<<m);s++){
		int cnt1=1;
		for(int j=1;j<=m;j++)
			if(s&(1<<(j-1)))
				cnt1=1ll*cnt1*a[j]%Mod;
		f[1][s]=cnt1;
	}
	for(int i=2;i<=m+1;i++){//gai
		for(int s=0;s<(1<<m);s++){
			for(int t0=s;t0;t0=(t0-1)&s){
				int t1=(s^t0),cnt=1;
				if(!f[i-1][t1]) continue;
				for(int j=1;j<=m;j++)
					if(t0&(1<<(j-1)))
						cnt=1ll*cnt*a[j]%Mod*a[j]%Mod;
				f[i][s]=(f[i][s]+1ll*f[i-1][t1]*cnt%Mod*(i-1)%Mod)%Mod;
			}
		}
		memcpy(h,f[i],sizeof(f[i]));
		for(int s=0;s<(1<<m);s++){
			for(int t0=s;t0;t0=(t0-1)&s){
				int t1=(s^t0),cnt=1;
				if(!f[i][t1]) continue;
				for(int j=1;j<=m;j++)
					if(t0&(1<<(j-1)))
						cnt=1ll*cnt*a[j]%Mod;
				h[s]=(h[s]+1ll*f[i][t1]*cnt%Mod)%Mod;
			}
		}
		memcpy(f[i],h,sizeof(f[i]));
	}
	f[1][0]=0,g[0][0]=1;
	int ans=0;
	for(int i=1;i<=2*m+1;i++)
		for(int s=1;s<(1<<m);s++){
			for(int j=1;j<=i;j++)
				for(int t0=s;t0;t0=(t0-1)&s){
					int t1=(s^t0);
					g[i][s]=(g[i][s]+1ll*g[i-j][t1]*f[j][t0]%Mod*C[i-1][j-1]%Mod)%Mod;
				}
			ans=(ans+g[i][s])%Mod;
		}
	printf("%d\n",ans);
	return 0;
}
//2446
//2462 x