#106503 (C++11) No.403 2^2^2

• 問題: No.403 2^2^2
• ユーザー: femto
• 提出日時: 2016-07-23 00:33:10
• 言語: C++11 (gcc 11.4.0)
• 結果: WA
• 実行時間: -
• コード長: 3,208 bytes
• コンパイル時間: 822 ms
• コンパイル使用メモリ: 70,780 KB
• 実行使用メモリ: 6,824 KB
• 最終ジャッジ日時: 2024-11-06 12:26:26
• 合計ジャッジ時間: 1,914 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-

ソースコード

#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cassert>
using namespace std;
typedef long long ll;

const int mod = 1000000007; // assert mod is prime

template<int M>
struct Mint {
	int x;
	Mint() : x(0) {}
	Mint(int y) : x(y >= 0 ? y % M : M - (-y) % M) {}
	Mint &operator += (const Mint &rhs) { if((x += rhs.x) >= M) x -= M; return *this; }
	Mint &operator -= (const Mint &rhs) { if((x += M - rhs.x) >= M) x -= M; return *this; }
	Mint &operator *= (const Mint &rhs) { x = 1LL * x*rhs.x % M; return *this; }
	Mint &operator /= (const Mint &rhs) { x = (1LL * x*rhs.inv().x) % M; return *this; }
	Mint operator - () const { return Mint(-x); }
	Mint operator + (const Mint &rhs) const { return Mint(*this) += rhs; }
	Mint operator - (const Mint &rhs) const { return Mint(*this) -= rhs; }
	Mint operator * (const Mint &rhs) const { return Mint(*this) *= rhs; }
	Mint operator / (const Mint &rhs) const { return Mint(*this) /= rhs; }
	bool operator < (const Mint &rhs) const { return x < rhs.x; }
	Mint inv() const {
		signed a = x, b = M, u = 1, v = 0, t;
		while(b) { t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); }
		return Mint(u);
	}
	Mint pow(long long t) const {
		Mint e = *this, res = 1;
		for(; t; e *= e, t >>= 1) if(t & 1) res *= e;
		return res;
	}
};
template <int M>
ostream &operator << (ostream &os, const Mint<M> &rhs) {
	return os << rhs.x;
}
template <int M>
istream &operator >> (istream &is, Mint<M> &rhs) {
	long long s; is >> s; rhs = Mint<M>(s); return is;
};

using mint = Mint<mod>;


ll modpow(ll x, ll y, ll m) {
	if(y == 0) return 1;
	ll res = modpow(x, y / 2, m);
	return res * res % m * (y & 1 ? x : 1) % m;
}

ll modinv(ll x, ll m) {
	return modpow(x, m - 2, m);
}

struct Comb {
	int sz;
	vector<mint> mfact, mfinv;
	Comb(int N) : sz(min(N, int(mod) - 1)), mfact(sz + 1), mfinv(sz + 1) {
		for(int i = 0; i <= sz; i++) mfact[i] = (i == 0 ? 1 : mfact[i - 1] * i);
		mfinv[sz] = mfact[sz].inv();
		for(int i = sz; i >= 1; i--) mfinv[i - 1] = mfinv[i] * i;
	}
	mint fact(int n, int& e) { // e に p の指数が入る
		// Wilson の定理
		e = 0;
		if(n <= sz) return mfact[n];
		mint res = fact(n / mod, e);
		e += n / mod;
		if(n / mod % 2 != 0) return -res * mfact[n % mod];
		return res * mfact[n % mod];
	}
	mint nPr(int n, int r) {
		int e; return fact(n, e) / fact(n - r, e);
	}
	mint nCr(int n, int r) {
		// Lucus の定理
		assert(n <= sz);
		if(n >= mod) return nCr(n%mod, r%mod) * nCr(n / mod, r / mod);
		return r > n ? 0 : mfact[n] * mfinv[n - r] * mfinv[r];
	}
	mint nHr(int n, int r) {
		return r == 0 ? 1 : nCr(n + r - 1, r);
	}
};

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	ll A, B, C;
	string s;
	cin >> s;

	int idx = s.find('^');
	cout << s.substr(0, idx) << endl;
	A = atoll(s.substr(0, idx).c_str());
	A %= mod;

	s = s.substr(idx + 1, s.size() - idx - 1);
	idx = s.find('^');
	B = atoll(s.substr(0, idx).c_str());
	s = s.substr(idx + 1, s.size() - idx - 1);
	C = atoll(s.c_str());

	ll Ab = modpow(A, B, mod);
	ll Bc = modpow(B, C, mod - 1);

	ll ans1 = modpow(Ab, C, mod);
	ll ans2 = modpow(A, Bc, mod);

	cout << ans1 << " " << ans2 << endl;
}