10pts 求条
查看原帖
10pts 求条
730195
Little_Cabbage楼主2024/11/4 16:11
#include <bits/stdc++.h>
#define int long long
using namespace std;

#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define fre(x) freopen(x".in", "r", stdin); freopen(x".out", "w", stdout);
#define deb(x) freopen(x".in", "r", stdin); freopen(x".ans", "w", stdout);

inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (ch > '9' || ch < '0') {
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (ch <= '9' && ch >= '0') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}

namespace chu {
	int a[3000010], b[3000010], c[3000010];
	
	inline void init(int a[], string s) {
		a[0] = s.length();
		for (int i = 1; i <= a[0]; i++)
			a[i] = s[a[0] - i] - 48;
	}
	
	inline void print(int a[], string &s) {
		if (a[0] == 0) {
			s = "0";
			return ;
		}
		for (int i = a[0]; i > 0; i--) s += a[i] + '0';
		return ;
	}
	
	inline int compare(int a[], int b[]) {
		if (a[0] > b[0])
			return 1;
		if (a[0] < b[0])
			return -1;
		for (int i = a[0]; i > 0; i--) {
			if (a[i] > b[i])
				return 1;
			if (a[i] < b[i])
				return -1;
		}
		return 0;
	}
	
	inline void jian(int a[], int b[]) {
		int flag;
		flag = compare(a, b);
		if (flag == 0) {
			a[0] = 0;
			return ;
		}
		if (flag == 1) {
			for (int i = 1; i <= a[0]; i++) {
				if (a[i] < b[i]) {
					a[i + 1]--;
					a[i] += 10;
				}
				a[i] -= b[i];
			}
			while (a[0] > 0 && a[a[0]] == 0)
				a[0]--;
			return ;
		}
	}
	
	inline void numcpy(int p[], int q[], int det) {
		for (int i = 1; i <= p[0]; i++)
			q[i + det - 1] = p[i];
		q[0] = p[0] + det - 1;
	}
	
	inline void chugao(int a[], int b[], int c[]) {
		int tmp[110];
		c[0] = a[0] - b[0] + 1;
		for (int i = c[0]; i > 0; i--) {
			memset(tmp, 0, sizeof(tmp));
			numcpy(b, tmp, i);
			while (compare(a, tmp) >= 0) {
				c[i]++;
				jian(a, tmp);
			}
		}
		while (c[0] > 0 && c[c[0]] == 0)
			c[0]--;
		return ;
	}
	
	inline pair<string, string> cmain(string xx, string yy) {
		memset(a, 0, sizeof(a));
		memset(b, 0, sizeof(b));
		memset(c, 0, sizeof(c));
		init(a, xx);
		init(b, yy);
		chugao(a, b, c);
		string x = "", y = "";
		print(c, x);
		print(a, y);
		return make_pair(x, y);
	}
}
using namespace chu;

namespace MUL {
	const int N = 3000000 + 10;
	const int M = 4e5 + 10;
	const int Mod = 1e9 + 9;
	const double PI = acos(-1);

	struct Complex {
		double x, y;
		Complex operator + (const Complex &other) const {
			return {x + other.x, y + other.y};
		} Complex operator - (const Complex &other) const {
			return {x - other.x, y - other.y};
		} Complex operator * (const Complex &other) const {
			return {x * other.x - y * other.y, x * other.y + y * other.x};
		}
	} a[N], b[N];
	string s1, s2;
	int res[N];
	int rev[N], bit, tot;

	inline void Init(string x, string y) {
		// cin >> s1 >> s2;
		s1 = x, s2 = y;
	}

	inline void FFT(Complex a[], int Inv) {
		for (int i = 0; i < tot; i ++ )
			if (i < rev[i])
				swap(a[i], a[rev[i]]);
		for (int mid = 1; mid < tot; mid <<= 1) {
			auto w1 = Complex({cos(PI / mid), Inv * sin(PI / mid)});
			for (int i = 0; i < tot; i += (mid << 1)) {
				auto wk = Complex({1, 0});
				for (int j = 0; j < mid; j ++, wk = wk * w1) {
					auto x = a[i + j], y = wk * a[i + j + mid];
					a[i + j] = x + y, a[i + j + mid] = x - y;
				}
			}
		}
	}

	int k;

	inline void Solve() {
		int n = s1.size() - 1, m = s2.size() - 1;
		for (int i = 0; i <= n; i ++ ) a[i].x = s1[n - i] - '0';
		for (int i = 0; i <= m; i ++ ) b[i].x = s2[m - i] - '0';
		while ((1 << bit) < n + m + 1) bit ++;
		tot = 1 << bit;
		for (int i = 0; i < tot; i ++ ) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
		FFT(a, 1), FFT(b, 1);
		for (int i = 0; i < tot; i ++ ) a[i] = a[i] * b[i];
		FFT(a, -1);
		k = 0;
		for (int i = 0, t = 0; i < tot || t; i ++ ) {
			t += a[i].x / tot + 0.5;
			res[k ++ ] = t % 10;
			t /= 10;
		}
		while (k > 1 && !res[k - 1]) k --;
		// for (int i = k - 1; i >= 0; i -- ) cout << res[i];
	}

	inline string mmain(string x, string y) {
		Init(x, y);
		Solve();
		string a = "";
		for (int i = k - 1; i >= 0; i -- ) a += res[i] + '0';
		return a;
	}
}
using namespace MUL;

namespace gjd {
	const int N = 3000000 + 10;
	
	int x[N], y[N], c[N * 2];
	
	inline string To_string(int x) {
		if (x == 0) return "0";
		string res = "";
		while (x) {
			res += x % 10 + '0';
			x /= 10;
		}
		reverse(res.begin(), res.end());
		return res;
	}
	
	inline string To_string(char x) {
		string res = "";
		res += x;
		return res;
	}
	
	inline int To_int(string s) {
		int res = 0;
		for (int i = 0; i < s.size(); i ++ ) res = res * 10 + s[i] - '0';
		return res;
	}
	
	inline string add(string a, string b) {
		int la = a.size();
		int lb = b.size();
		for (int i = la - 1; i >= 0; i -- ) x[la - i] = a[i] - '0';
		for (int i = lb - 1; i >= 0; i -- ) y[lb - i] = b[i] - '0';
		int lc = 1;
		int delta = 0;
		while (lc <= la && lc <= lb) {
			int t = x[lc] + y[lc] + delta;
			c[lc] = t % 10;
			delta = t / 10;
			lc ++ ;
		}
		while (lc <= la) {
			int t = x[lc] + delta;
			c[lc] = t % 10;
			delta = t / 10;
			lc ++ ;
		}
		while (lc <= lb) {
			int t = y[lc] + delta;
			c[lc] = t % 10;
			delta = t / 10;
			lc ++ ;
		}
		while (c[lc] == 0 && lc > 1) lc -- ;
		string res = "";
		for (int i = lc; i >= 1; i -- ) res += c[i] + '0';
		return res;
	}
	
	inline string mul(string a, int b) {
		string res = "";
		int delta = 0;
		for (int i = a.size() - 1; i >= 0; i -- ) {
			int t = (a[i] - '0') * b + delta;
			res += t % 10 + '0';
			delta = t / 10;
		}
		if (delta) res += delta + '0';
		reverse(res.begin(), res.end());
		return res;
	}
	
	inline int cnt0(string s) {
		int cnt = 0;
		for (int i = s.size() - 1; i >= 0; i -- ) {
			if (s[i] == '0') cnt ++ ;
			else break;
		}
		return cnt;
	}
	
	inline string mul(string a, string b, int op) {
		int cnt = cnt0(b);
		while (cnt -- ) a += '0';
		return a;
	}
	
	inline string mul(string a, string b) {
		string res = "0";
		string pw = "1";
		for (int i = b.size() - 1; i >= 0; i -- ) {
			res = add(res, mul(mul(a, To_int(To_string(b[i]))), pw, 1));
			pw = mul(pw, "10", 1);
		}
		return res;
	}
	
	inline bool dy(string a, string b) {
		int la = a.size(), lb = b.size();
		if (la > lb) return true;
		if (la < lb) return false;
		for (int i = 0; i < la; i ++ ) {
			if (a[i] > b[i]) return true;
			if (a[i] < b[i]) return false;
		}
		return true;
	}
	
	inline string jf(string a, string b) {
		reverse(a.begin(), a.end());
		reverse(b.begin(), b.end());
		int la = a.size(), lb = b.size();
		int delta = 0;
		string res = "";
		for (int i = lb; i < la; i ++ ) b += '0';
		for (int i = 0; i < la; i ++ ) {
			int t = (a[i] - '0') - (b[i] - '0');
			if (t < 0) {
				t += 10;
				a[i + 1] -- ;
			}
			res += t + '0';
		}
		int lc = 0;
		for (int i = 0; i < res.size(); i ++ ) c[ ++ lc] = res[i] - '0';
		while (lc > 1 && c[lc] == 0) lc -- ;
		if (lc == 0) return "0";
		res = "";
		for (int i = 1; i <= lc; i ++ ) res += c[i] + '0';
		reverse(res.begin(), res.end());
		return res;
	}
	
	inline pair<string, string> div_and_mod(string a, string b) {//
		string now = "0";
		int la = a.size(), lb = b.size();
		string res = "0";
		cout << la - 1 << "\n";
		for (int i = 0; i < la; i ++ ) {
			now = add(mul(now, "10"), To_string(a[i]));
			if (dy(now, b)) {
				int k = 1;
				while (dy(now, mul(To_string(k), b))) {
					k ++ ;
					// cout << now << " > " << mul(To_string(k), b) << "\n";
				}
				k -- ;
				cout << mul(res, "10") << " + " << To_string(k) << " = ";
				res = add(mul(res, "10"), To_string(k));
				cout << res << "\n" << now << " - " << mul(b, To_string(k)) << " = ";
				now = jf(now, mul(b, To_string(k)));
				cout << now << "\n";
			}
			cout << "i: " << i << " res: " << res << " now: " << now << "\n";
		}
		return make_pair(res, now);
	}
	
	inline int gcd(int a, int b) {
		if (a == 0) return b;
		return gcd(b % a, a);
	}
	
	inline string gcd(string a, string b) {
		if (a == "0") return b;
		pair<string, string> t = cmain(b, a);
		// cout << t.second << "\n";
		return gcd(t.second, a);
	}
}
using namespace gjd;

namespace zla {
	int n, m;
	
	inline void Clear() {
		;
	}
	
	inline void Init() {
		n = read(), m = read();
	}
	
	inline void Solve() {
		string a = "1", b = "1";
		// cout << "a: " << a << " b: " << b << "\n";
		for (int i = 1; i <= m - 1; i ++ ) a = mmain(a, To_string(i));
		for (int i = n + 1; i <= n + m - 1; i ++ ) b = mmain(b, To_string(i));
		// cout << a << " " << b << "\n";
		// /*
		string x = jf(b, a);
		// cout << "x: " << x << "\n";
		string y = mmain(mmain(To_string(m - 1), a), b);
		// cout << "y: " << y << "\n";
		string g = gcd(x, y);
		// cout << "gcd: " << g << "\n";
		pair<string, string> t1 = cmain(x, g), t2 = cmain(y, g);
		// cout << x << "\n" << y << "\n";
		// cout << "-----------\n";
		cout << t1.first << "\n" << t2.first << "\n";
		// */
	}
	
	inline void main() {
		Clear();
		Init();
		Solve();
	}
}

signed main() {
	// IOS;
	// fre("sum");
	// deb("sum");
	int T = 1;
	// cin >> T;
	while (T -- ) zla::main();
	return 0;
}
/*
1 * 2 * 3 * ... * n = n!

*/

2024/11/4 16:11
加载中...