WA 求助
查看原帖
WA 求助
1058410
Gcc_Gdb_7_8_1楼主2025/2/3 18:51
#include <bits/stdc++.h>
#ifndef __DEBUG_LIB
#define __DEBUG_LIB

bool isdebug = false;

#define change(x) isdebug = x
#define Debugc if(isdebug) cout
#define Debug if(isdebug)

#endif
using namespace std;

#define LL long long
#define Pii pair<int, int>
#define ULL unsigned long long
//#define ONLINE_JUDGE luogu

namespace gdb7
{
	class Bigint {
		private:
			static constexpr int indbase = 18;
			static const LL base = pow(10, indbase);
			vector<LL> v;
		public:
			void read() {
				string str;
				cin >> str;
				while (str.size() % indbase != 0) {
					str = "0" + str;
				}
				for (int i = str.size() - indbase; i >= 0; i -= indbase) {
					v.push_back(stoll(str.substr(i, indbase)));
				}
			}
			void write() const {
				for (int i = v.size() - 1; i >= 0; --i) {
					if (i == v.size() - 1) {
						cout << v[i];
					} else {
						cout << setfill('0') << setw(indbase) << v[i];
					}
				}
				cout << '\n';
			}
			const Bigint operator+(const Bigint &rhs) const {
				Bigint ans;
				for (int i = 0; i <= max(rhs.v.size(), v.size()); ++i) {
					ans.v.push_back(0);
				}
				for (int i = 0; i < min(rhs.v.size(), v.size()); ++i) {
					ans.v[i] += rhs.v[i] + v[i];
					ans.v[i + 1] += ans.v[i] / base;
					ans.v[i] %= base;
				}
				for (int i = min(rhs.v.size(), v.size()); i < max(rhs.v.size(), v.size()); ++i) {
					ans.v[i] += (rhs.v.size() > v.size() ? rhs.v : v)[i];
					ans.v[i + 1] += ans.v[i] / base;
					ans.v[i] %= base;
				}
				while (!ans.v[ans.v.size() - 1] && ans.v.size() > 1) {
					ans.v.pop_back();
				}
				return ans;
			}
			const Bigint operator-(const Bigint &rhs) const {
				Bigint ans;
				for (int i = 0; i < v.size(); ++i) {
					ans.v.push_back(0);
				}
				for (int i = 0; i < rhs.v.size(); ++i) {
					ans.v[i] += v[i] - rhs.v[i];
					if (ans.v[i] < 0) {
						--ans.v[i + 1];
						ans.v[i] += base;
					}
				}
				for (int i = rhs.v.size(); i < v.size(); ++i) {
					ans.v[i] += v[i];
				}
				while (!ans.v[ans.v.size() - 1] && ans.v.size() > 1) {
					ans.v.pop_back();
				}
				return ans;
			}
			const Bigint operator*(const Bigint &rhs) const {
				Bigint ans;
				if (v.size() <= 100 && rhs.v.size() <= 100) {
					for (int i = 0; i < v.size() + rhs.v.size(); ++i) {
						ans.v.push_back(0);
					}
					for (int i = 0; i < v.size(); ++i) {
						for (int j = 0; j < rhs.v.size(); ++j) {
//							cout << i << " " << j << endl;
							ans.v[i + j] += v[i] * rhs.v[j];
							ans.v[i + j + 1] += ans.v[i + j] / base;
							ans.v[i + j] %= base;
						}
					}
					while (!ans.v[ans.v.size() - 1] && ans.v.size() > 1) {
						ans.v.pop_back();
					}
				} else {
					Bigint a, b, c, d;
					const int cut = (max(rhs.v.size(), v.size()) >> 1);
					for (int i = cut; i < v.size(); ++i) {
						a.v.push_back(v[i]);
					}
					for (int i = 0; i < cut; ++i) {
						b.v.push_back(v[i]);
					}
					for (int i = cut; i < rhs.v.size(); ++i) {
						c.v.push_back(rhs.v[i]);
					}
					for (int i = 0; i < cut; ++i) {
						d.v.push_back(rhs.v[i]);
					}
					Bigint ac = a * c, bd = b * d;
					Bigint e = (a + b) * (c + d) - ac - bd;
					ans.v.insert(ans.v.end(), ac.v.begin(), ac.v.end()); /*****/
					ans.v.insert(ans.v.end(), e.v.begin(), e.v.end()); /*****/
					ans.v.insert(ans.v.end(), bd.v.begin(), bd.v.end()); /*****/
				}
				return ans;
			} 
	};
	signed main() {
//		freopen("C:/Users/42175/OneDrive/Desktop/Luogu Problem Data/P1919_1.in", "r", stdin);
//		freopen("myout.out", "w", stdout);
		ios::sync_with_stdio(false);
		cin.tie(0);
		Bigint a, b;
		a.read();
		b.read();
		Bigint c = a * b;
		c.write();
	    return 0;
	}
};

signed main()
{
	return gdb7::main();
}

该代码在提交时会 TLE,咱先不管。

将第一个测试点下载下来后,测试发现 WA,疑似标记 /*****/ 的地方有问题。

因为公式为 Ans=ACx2+(AD+BC)x+BDAns = ACx^2 + (AD + BC)x + BD,但这里写的是压位高精(其实还要指令集优化,否则如上文,会 TLE),无法直接在数字的末尾插入 0,所以只能试试直接将三个数拼起来,但这就会 WA,有没有办法替代。

2025/2/3 18:51
加载中...