题目大意

给出一个数 \(n\)，你要构造一个数列，满足里面每个数都是 \(n\) 的因子，且每一个数与前面不互质的个数不超过 \(1\)。问有多少种合法方案。

保证 \(n\) 的不同质因子个数 \(\le 6\)。

思路

这个题不是很难，只是比较难写。不过 \(\Theta(6\times 3^6)\) 的做法感觉比较有意思，但是我写的是玄学时间复杂度的做法。

我们可以看出数列长度最大也就 \(12\)，而且质因子个数也很少，不难想到状压 dp，我们发现这个状压 dp 完全没有什么难点，直接 \(f_{S,x}\) 表示当前状态为 \(S\)，已经填了 \(x\) 位的方案数。对于一个状态，肯定是每个质因子的状态组合起来，你发现重要的不过就是这个质因子出现了几次，如果只出现一次是哪些质因子一起出现的。你把这个压进状态就好了。

似乎预处理了之后转移可以更快，但是懒得了。

\(\texttt{Code}\)

#include <bits/stdc++.h>

using namespace std;

#define Int register int

#define mod 1000000007

#define ll long long

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}

template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}

template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}

ll N;

int cnt,yz[15],pw[15];

int mul (int a,int b){return 1ll * a * b % mod;}

int dec (int a,int b){return a >= b ? a - b : a + mod - b;}

int add (int a,int b){return a + b >= mod ? a + b - mod : a + b;}

void Mul (int &a,int b){a = mul (a,b);}

void Dec (int &a,int b){a = dec (a,b);}

void Add (int &a,int b){a = add (a,b);}

void Makeyz (ll n){

	for (Int i = 2;1ll * i * i <= n;++ i){

		if (n % i == 0){

			yz[++ cnt] = i;

			while (n % i == 0) n /= i,pw[cnt] ++;

		}

	}

	if (n > 1) yz[++ cnt] = n,pw[cnt] = 1;

} 

int f[1 << 19][15];

signed main(){

	read (N),Makeyz (N);

	f[0][0] = 1;int ans = 0;

	for (Int x = 0;x < cnt * 2;++ x){

		for (Int nowS = 0;nowS < (1 << cnt * 3);++ nowS){

			if (!f[nowS][x]) continue;

			vector <int> unused,cho;

			bool used[12] = {};

			for (Int i = 1;i <= cnt;++ i){

				int k = nowS >> (i - 1) * 3 & 7;

				if (!k) unused.push_back (i);

				else if (k < 7 && !used[k]) cho.push_back (i),used[k] = 1;

			}

			int siz1 = unused.size(),siz2 = cho.size();

			for (Int S = 0;S < (1 << siz1);++ S){

				int kase = 1,S1 = 0,fir = 0;

				for (Int i = 0;i < siz1;++ i) if (S >> i & 1)

					fir = fir ? fir : unused[i],Mul (kase,pw[unused[i]]),S1 |= (1 << (unused[i] - 1) * 3) * fir;

				if (S) Add (f[nowS | S1][x + 1],mul (kase,f[nowS][x]));

				if (!cho.size()) continue;

				for (Int u : cho){

					int k = nowS >> (u - 1) * 3 & 7,siz2 = 0;

					vector <int> uni;

					for (Int i = 1;i <= cnt;++ i) if ((nowS >> (i - 1) * 3 & 7) == k) uni.push_back (i);

					siz2 = uni.size();

					for (Int choS = 1;choS < (1 << siz2);++ choS){

						int newS = nowS | S1,fir = 0x7f7f7f7f,kase1 = 1;

						for (Int i = 0;i < siz2;++ i)

							if (choS >> i & 1) newS -= (1 << (uni[i] - 1) * 3) * (k - 7),Mul (kase1,pw[uni[i]]);

							else fir = min (fir,uni[i]);

						for (Int i = 0;i < siz2;++ i) if (!(choS >> i & 1)) newS -= (1 << (uni[i] - 1) * 3) * (k - fir);

						Add (f[newS][x + 1],mul (f[nowS][x],mul (kase,kase1)));

					}

				}

			}

		}

	}

	for (Int x = 1;x <= cnt * 2;++ x) for (Int nowS = 0;nowS < (1 << cnt * 3);++ nowS) Add (ans,f[nowS][x]);

	write (ans),putchar ('\n');

	return 0;

}

巴特西

题解 2020.10.24 考试 T3 数列

题目大意

思路

\(\texttt{Code}\)

最新文章

热门文章