序列[2020联考][dp]

题目

思路

可以发现对于一个素数最多$2$ 个数拥有
然后这两个数连边
发现向前只有 $1$ 条边
那么转化成森林方案数
首先计算一棵树的方案数
$$f_{iS}:i个节点素数占用集合为S树的方案数$$
转移要么连边要么自己加
然后
$g_{iS}: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

本文地址：https://blog.csdn.net/qq_37555704/article/details/109261926