MnZn 高精快速幂求调
  • 板块学术版
  • 楼主Albert_Wei
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/8/8 14:41
  • 上次更新2023/11/3 05:12:07
查看原帖
MnZn 高精快速幂求调
676634
Albert_Wei楼主2023/8/8 14:41
#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;

namespace Poly {
  const double Pi = acos(-1);
  struct comp {
  	double x, y;
  	comp (double xx = 0, double yy = 0) {x = xx, y = yy;}
  };
  comp operator + (comp x, comp y) {return comp(x.x + y.x, x.y + y.y);}
  comp operator - (comp x, comp y) {return comp(x.x - y.x, x.y - y.y);}
  comp operator * (comp x, comp y) {return comp(x.x * y.x - x.y * y.y, x.x * y.y + x.y * y.x);}
  int num[4000005];
  comp arr[4000005];
  inline void FFT(comp *A, int Lim, int flag) {
  	for (int i = 0; i < Lim; i++) num[i] = (num[i >> 1] >> 1) | ((i & 1) * (Lim >> 1));
  	for (int i = 0; i < Lim; i++) if (i < num[i]) swap(A[i], A[num[i]]);
  	for (int len = 1; len < Lim; len <<= 1) {
  	  comp w = comp(cos(Pi / len), sin(Pi / len) * flag);
  	  for (int i = 0; i < Lim; i += (len << 1)) {
  	  	comp w0 = comp(1, 0);
  	  	for (int j = i; j < i + len; j++, w0 = w0 * w) {
  	  	  comp g = A[j], h = A[j + len] * w0;
  	  	  A[j] = g + h, A[j + len] = g - h;
		}
	  }
	}
  }
  inline vector<int> Mul(vector<int> a, vector<int> b) {
  	vector<int> ans(a.size() + b.size() - 1);
  	for (int i = 0; i < a.size(); i++) arr[i].x = a[i];
  	for (int i = 0; i < b.size(); i++) arr[i].y = b[i];
  	int len = 1; while (len < a.size() + b.size()) len <<= 1;
  	FFT(arr, len, 1); for (int i = 0; i < len; i++) arr[i] = arr[i] * arr[i]; FFT(arr, len, -1);
  	for (int i = 0; i <= a.size() + b.size() - 2; i++) ans[i] = (int)(arr[i].y / 2 / len + 0.5);
  	return ans;
  }
}

namespace BigIntHelper {
  struct BigInt {vector<int> num;};
  inline BigInt Build (vector<int> x) {BigInt ans; ans.num = x; return ans;}
  inline istream& operator >> (istream &cin_, BigInt &x) {
  	char ch; ch = getchar();
  	while (ch < '0' || ch > '9') ch = getchar();
  	while (ch >= '0' && ch <= '9')
	  x.num.push_back((int)(ch - '0')), ch = getchar();
  	return cin_;
  }
  inline ostream& operator << (ostream &cout_, BigInt x) {
  	for (auto i : x.num) cout << i;
  	return cout_;
  }
  inline bool equ(BigInt x) {
  	vector<int> zero(1, 0);
  	return (x.num == zero);
  }
  inline long long I2ll (BigInt x) {
  	long long ans = 0;
  	for (auto i : x.num) ans = ans * 10 + i;
  	return ans;
  }
  inline BigInt ll2I (long long x) {
  	vector<int> ans;
  	if (!x) ans.push_back(0);
  	while (x) ans.push_back(x % 10), x /= 10;
  	reverse(ans.begin(), ans.end());
  	return Build(ans);
  }
  inline BigInt operator + (BigInt x, BigInt y) {
  	int n = x.num.size(), m = y.num.size();
  	vector<int> ans(max(n, m), 0);
  	reverse(x.num.begin(), x.num.end());
  	reverse(y.num.begin(), y.num.end());
  	for (int i = 0; i < n; i++) ans[i] += x.num[i];
  	for (int i = 0; i < m; i++) ans[i] += y.num[i];
  	for (int i = 0; i <= max(n, m) - 2; i++) ans[i + 1] += ans[i] / 10, ans[i] %= 10;
  	if (ans[ans.size() - 1] > 10) ans.push_back(ans[ans.size() - 1] / 10), ans[ans.size() - 2] %= 10;
  	reverse(ans.begin(), ans.end());
  	return Build(ans);
  }
  inline BigInt operator * (BigInt x, BigInt y) {
  	if (equ(x) || equ(y)) return ll2I(0);
  	vector<int> ans = Poly::Mul(x.num, y.num);
	reverse(ans.begin(), ans.end());
  	for (int i = 0; i <= (int)(ans.size()) - 2; i++) ans[i + 1] += ans[i] / 10, ans[i] %= 10;
  	while (ans[ans.size() - 1] > 10) ans.push_back(ans[ans.size() - 1] / 10), ans[ans.size() - 2] %= 10;
  	reverse(ans.begin(), ans.end());
  	return Build(ans);
  }
  inline BigInt qpow(BigInt x, BigInt y) {
  	int p = I2ll(y);
  	BigInt ans = ll2I(1ll);
  	while (p) {
  	  if (p & 1) ans = ans * x;
  	  x = x * x, p >>= 1;
	}
	return ans;
  }
}
using namespace BigIntHelper;

#define int BigInt

signed main() {
  cout << qpow(ll2I(2), ll2I(100)) << endl;
  return 0;
}

rt,输出

8384883669867978008-88-88-88-88-88-88-88-88-88-88-88-88-99-29-39-64-41-89-40-70-68-8
2023/8/8 14:41
加载中...