21.10.27模拟 P4157 [SCOI2006]整数划分

证明见luogu，我是打表发现这个规律的。但是这个规律也很显然吧。任何大于5的自然数都可以拆成若干个2,3的和，拆成2，3再乘肯定更大

namespace solve {
	int num2, num3;
	const int Len = 1007, W = 1000000000;

	struct hp {
		lxl x[Len];
		int siz;
		inline void trim() {
			while(siz && !x[siz - 1])--siz;
		}
		hp(lxl a = 0) {
			memset(x, 0, sizeof x);
			siz = 0;
			while(a) {
				x[siz++] = a % W;
				a /= W;
			}
		}
	} ans, p, q, res;

	inline void operator +=(hp &a, const hp &b) {
		a.siz = max(a.siz, b.siz) + 1;
		rep(i, 0, a.siz - 1) {
			a.x[i] += b.x[i];
		}
		rep(i, 0, a.siz - 1) {
			if(a.x[i] >= W) {
				++a.x[i + 1];
				a.x[i] -= W;
			}
		}
		a.trim();
	}
	inline hp operator +(hp a, const hp &b) {
		a += b;
		return a;
	}

	inline hp operator *(const hp &a, const hp &b) {
		hp c;
		c.siz = b.siz + a.siz;
		rep(i, 0, a.siz - 1) {
			rep(j, 0, b.siz - 1) {
				int k = i + j;
				c.x[k] += a.x[i] * b.x[j];
				c.x[k + 1] += c.x[k] / W;
				c.x[k] %= W;
			}
		}
		c.trim();
		return c;
	}
	inline int get(lxl x) {
		int num(0);
		while(x) {
			num++;
			x /= 10;
		}
		return num;
	}

	inline std::string tr(lxl x) {
		std::string s = "";
		while(x) {
			s += x % 10 + '0';
			x /= 10;
		}
		reverse(s.begin(), s.end());
		return s;
	}


	inline void Write(const hp &a) {

		int num(0);
		lxl r(a.x[a.siz - 1]);
		num = get(r);
		cout << (a.siz - 1) * 9 + num << '
';
		std::string s = "";
		s += tr(a.x[a.siz - 1]);

		drp(i, a.siz - 2, 0) {
			num = get(a.x[i]);
			while(num < 9) {
				s += '0';
				++num;
			}
			s += tr(a.x[i]);
		}
		int t = s.size() - 1;
		rep(i, 0, min(99, t))
		cout << s[i];
		cout << '
';
	}


	int main() {

		if(n == 1 || n == 2) {
			cout << 1 << '
' << n << '
';
			return 0;
		}

		int t = n % 3;
		if(t == 1) {
			num2 = 2;
		} else if(t == 2) {
			num2 = 1;
		} else {
			num2 = 0;
		}
		num3 = (n - num2 * 2) / 3;
		p = 2;
		q = 3;
		res = 1;

		ans = 1;

		if(num2) {
			while(num2 > 1) {
				p = p * 2;
				--num2;
			}
			ans = ans * p;
		}
		if(num3) {
			while(num3 > 1) {
				q = q * 3;
				--num3;
			}
			ans = ans * q;
		}
		Write(ans);
		return 0;
	}
}