题解 Six（留坑）

考场上搞了个三进制状压，结果正确性假了……

有想到从约数下手，但觉得就光预处理约数复杂度就爆炸就没往这边想……

首先是关于约数个数的证明，再一次感谢战神：

因为 \(n = \prod p_i^{c_i}\) ，最坏情况下 \(p_i=2\) ，这时有 \(\sum c_i \leqslant 50\)

因为 \(num(p_i) \leqslant 6\) ，所以约数个数（大致上） \(\leqslant (\frac{50}{6})^6 \approx 3\times10^5\)

留个坑吧，我那本组合极值（？）呢

事实上我数组只开了 \(1e5\) 也过了

然后考虑爆搜模拟加数过程

发现需要能够判断一对质因子对有没有出现在不同的数中

举个例子，2 3加入6时要判断2和3是不是来自于同一个数

所以再用一个二进制串，每一位代表某对质因子是否在不同的数中出现过

然后这个dfs就很好记忆化了

然而我质因数分解的判断条件i*i<=n忘写等号了……

至于这里的状态数，题解里说“可以证明” \(\leqslant 50000\) 种，然而不会证……

实测数据中状态数最大的一个点有 \(3267\) 种状态

口胡下是因为每个状态要想发生变化必须加入新的质因子，而受质因子个数限制这个过程最多重复6次？不会证……

upd：感谢@Rings（抱歉我不知道您的id……）提供的柿子：这个状态数应该是 \(\sum\limits_{i=1}^6 {6 \choose 2} 2^{i\choose 2} \approx 4 \times 10^4\)

Code:

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define N 100010

#define ll long long

#define reg register int

#define fir first

#define sec second

#define make make_pair

//#define int long long 

char buf[1<<21], *p1=buf, *p2=buf;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)

inline ll read() {

	ll ans=0, f=1; char c=getchar();

	while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}

	while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}

	return ans*f;

}

ll n;

ll h[10];

const ll mod=1e9+7;

namespace force{

	ll p[10], c[10], cnt, ans;

	ll dp[N];

	void init(ll n) {

		ll i;

		//cout<<2<<endl;

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

			//cout<<i<<endl;

			if (!(n%i)) {

				p[++cnt]=i;

				//cout<<"add "<<i<<' '<<n/i<<endl;

				do {n/=i; ++c[cnt];} while (!(n%i));

			}

		}

		//cout<<1<<endl;

		if (n>1) p[++cnt]=n, c[cnt]=1;

		//cout<<"cnt: "<<cnt<<endl;

		//for (int i=1; i<=cnt; ++i) cout<<p[i]<<' '; cout<<endl;

		//for (int i=1; i<=cnt; ++i) cout<<c[i]<<' '; cout<<endl;

	}

	ll qpow(ll a, ll b) {

		ll ans=1;

		while (b) {

			if (b&1) ans=ans*a%mod;

			a=a*a%mod; b>>=1;

		}

		return ans;

	}

	void solve() {

		init(n);

		h[0]=1;

		for (int i=1; i<=9; ++i) h[i]=h[i-1]*3;

		int t[10], num; ll pi[10];

		int lim=h[cnt], lim2=1<<cnt;

		//cout<<"lim: "<<lim<<' '<<lim2<<endl;

		ll cnt2;

		for (int i=1; i<lim2; ++i) {

			cnt2=0;

			for (int j=0; j<cnt; ++j) if (i&(1<<j)) {

				cnt2+=c[j+1]-1;

			}

			pi[i]=qpow(2, cnt2);

			//cout<<"pi: "<<bitset<3>(i)<<' '<<pi[i]<<endl;

		}

		dp[0]=1;

		memset(t, 0, sizeof(t));

		for (int s=0; s<lim; ++s) {

			num=0;

			for (int i=0; i<cnt; ++i) num+=t[i]*h[i];

			//cout<<"num: "<<num<<endl;

			for (int i=1,tem; i<lim2; ++i) {

				tem=0;

				for (int j=0; j<cnt; ++j) if (i&(1<<j)) {

					if (t[j]==2) goto jump;

					else tem+=h[j];

				}

				if (cnt==2 && t[0]==1 && t[1]==1 && i==3) {

					dp[num+tem]=(dp[num+tem]+((dp[num]-dp[1]-dp[3])%mod+mod)%mod*pi[i]%mod)%mod;

				}

				else dp[num+tem]=(dp[num+tem]+dp[num]*pi[i]%mod)%mod;

				jump: ;

			}

			//cout<<"dp"; for (int i=0; i<cnt; ++i) cout<<t[i]; cout<<": "<<dp[num]<<endl;

			if (num) ans=(ans+dp[num])%mod;

			++t[0];

			for (int i=0; i<cnt; ++i)

				if (t[i]>=3) ++t[i+1], t[i]-=3;

				else break;

		}

		printf("%lld\n", ((ans)%mod+mod)%mod);

		exit(0);

	}

}

namespace task{

	ll p[10], c[10], div[N];

	int ds[N], pcnt, dcnt, tran[10][10], pr[1<<7];

	struct pair_hush{inline size_t operator () (pair<int, int> p) const {return hash<ll>()(1ll*p.fir*p.sec+p.fir);}};

	unordered_map<pair<int, int>, ll, pair_hush> mp{5000, pair_hush()};

	void dfs1(int u, ll sum, int s) {

		//cout<<"dfs1 "<<u<<' '<<sum<<' '<<s<<endl;

		if (u>pcnt) {if (sum!=1) div[++dcnt]=sum, ds[dcnt]=s; return ;}

		dfs1(u+1, sum, s);

		for (reg i=1; i<=c[u]; ++i)

			dfs1(u+1, sum*p[u], s|(1<<(u-1)));

	}

	void init(ll n) {

		ll i;

		for (i=2; i*i<=n; ++i)

			if (!(n%i)) {

				p[++pcnt]=i;

				do {n/=i; ++c[pcnt];} while (!(n%i));

			}

		if (n>1) p[++pcnt]=n, c[pcnt]=1;

		//cout<<"pcnt: "<<pcnt<<endl;

		//cout<<"p: "; for (int i=1; i<=pcnt; ++i) cout<<p[i]<<' '; cout<<endl;

		dfs1(1, 1, 0);

		//cout<<"dcnt: "<<dcnt<<endl;

		//for (int i=1; i<=dcnt; ++i) cout<<div[i]<<' '<<bitset<5>(ds[i])<<endl;

		int tot=0;

		for (reg i=0; i<pcnt; ++i)

			for (reg j=i; j<pcnt; ++j)

				tran[i][j]=tran[j][i]=1<<(tot++);

		//cout<<"tot: "<<tot<<endl;

		int lim=1<<pcnt;

		for (reg s=1; s<lim; ++s)

			for (reg i=0; i<pcnt; ++i) if (s&(1<<i))

				for (reg j=0; j<pcnt; ++j) if (s&(1<<j))

					pr[s]|=tran[i][j];

	}

	ll dfs(int s, int t) {

		//cout<<"dfs "<<bitset<5>(s)<<' '<<bitset<5>(t)<<endl;

		if (mp.find(make(s, t))!=mp.end()) return mp[make(s, t)];

		ll ans=0;

		for (int i=1,s2; i<=dcnt; ++i) {

			s2=s&ds[i];

			if (!(t&pr[s2])) {

				s2=0;

				for (reg j=0; j<pcnt; ++j) if (ds[i]&(1<<j))

					for (reg k=0; k<pcnt; ++k) if (s&(1<<k))

						s2|=tran[j][k];

				ans=(ans+dfs(s|ds[i], t|s2))%mod;

			}

		}

		//cout<<"return "<<bitset<5>(s)<<' '<<bitset<5>(t)<<' '<<ans+1<<endl;

		mp[make(s, t)]=ans+1;

		return ans+1;

	}

	void solve() {

		init(n);

		printf("%lld\n", dfs(0, 0)-1);

		exit(0);

	}

}

signed main()

{

	n=read();

	//force::solve();

	task::solve();

	return 0;

}

巴特西

题解 Six（留坑）

最新文章

热门文章