文章目录
- 题目
- 思路
- 代码
题目
思路
可以发现对于一个素数最多
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
本文地址:https://blog.csdn.net/qq_37555704/article/details/109261926