#124455 (C++11) No.434 占い

• 問題: No.434 占い
• ユーザー: pekempey
• 提出日時: 2016-10-17 04:20:23
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 158 ms / 2,000 ms
• コード長: 2,427 bytes
• コンパイル時間: 1,858 ms
• コンパイル使用メモリ: 176,528 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-05-02 02:57:09
• 合計ジャッジ時間: 3,853 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	9 ms; 5,248 KB
testcase_01	AC	9 ms; 5,376 KB
testcase_02	AC	9 ms; 5,376 KB
testcase_03	AC	9 ms; 5,376 KB
testcase_04	AC	9 ms; 5,376 KB
testcase_05	AC	9 ms; 5,376 KB
testcase_06	AC	10 ms; 5,376 KB
testcase_07	AC	9 ms; 5,376 KB
testcase_08	AC	11 ms; 5,376 KB
testcase_09	AC	10 ms; 5,376 KB
testcase_10	AC	10 ms; 5,376 KB
testcase_11	AC	12 ms; 5,376 KB
testcase_12	AC	25 ms; 5,376 KB
testcase_13	AC	10 ms; 5,376 KB
testcase_14	AC	10 ms; 5,376 KB
testcase_15	AC	18 ms; 5,376 KB
testcase_16	AC	17 ms; 5,376 KB
testcase_17	AC	18 ms; 5,376 KB
testcase_18	AC	20 ms; 5,376 KB
testcase_19	AC	32 ms; 5,376 KB
testcase_20	AC	158 ms; 5,376 KB
testcase_21	AC	18 ms; 5,376 KB
testcase_22	AC	17 ms; 5,376 KB
testcase_23	AC	9 ms; 5,376 KB
testcase_24	AC	18 ms; 5,376 KB
testcase_25	AC	18 ms; 5,376 KB
testcase_26	AC	13 ms; 5,376 KB
testcase_27	AC	19 ms; 5,376 KB
testcase_28	AC	19 ms; 5,376 KB
testcase_29	AC	38 ms; 5,376 KB
testcase_30	AC	127 ms; 5,376 KB

ソースコード

#include <bits/stdc++.h>
using namespace std;

struct CombinationAnyMod {
	struct CombinationPrimePower {
		int p, q;
		int mod;
		vector<int> F, invF, power, e;

		static pair<int, int> extgcd(int a, int b) {
			if (b == 0) return make_pair(1, 0);
			int x, y;
			tie(x, y) = extgcd(b, a % b);
			return make_pair(y, x - a / b * y);
		}

		static int modulo(int a, int mod) {
			return (a %= mod) < 0 ? a + mod : a;
		}

		static int modinv(int a, int mod) {
			return modulo(extgcd(a, mod).first, mod);
		}

		int mul(int x, int y) {
			return int64_t(x) * y % mod;
		}

		CombinationPrimePower(int n, int p, int q) : p(p), q(q), F(n), invF(n), e(n), power(q + 1) {
			mod = 1;
			for (int i = 0; i < q; i++) mod *= p;

			power[0] = 1;
			for (int i = 1; i <= q; i++) power[i] = mul(power[i - 1], p);

			F[0] = 1;
			for (int i = 1; i < n; i++) {
				F[i] = mul(F[i - 1], i % p == 0 ? 1 : i);
			}

			invF[n - 1] = modinv(F[n - 1], mod);
			for (int i = n - 2; i >= 0; i--) {
				invF[i] = mul(invF[i + 1], (i + 1) % p == 0 ? 1 : i + 1);
			}

			for (int i = 1; i < n; i++) {
				F[i] = mul(F[i], F[i / p]);
				invF[i] = mul(invF[i], invF[i / p]);
				e[i] = i / p + e[i / p];
			}
		}

		int operator()(int n, int r) {
			if (n < 0 || r < 0 || n < r) return 0;
			int f = mul(F[n], mul(invF[n - r], invF[r]));
			return mul(f, power[min(q, e[n] - e[n - r] - e[r])]);
		}
	};

	map<int, int> prime_factors(int n) {
		map<int, int> res;
		for (int i = 2; i * i <= n; i++) {
			for (; n % i == 0; n /= i) res[i]++;
		}
		if (n != 1) res[n] = 1;
		return res;
	}

	vector<CombinationPrimePower> cs;
	vector<int> inv;

	CombinationAnyMod(int n, int mod) {
		for (auto kv : prime_factors(mod)) {
			cs.emplace_back(n, kv.first, kv.second);
		}
		int m = 1;
		for (auto &c : cs) {
			inv.push_back(CombinationPrimePower::modinv(m, c.mod));
			m *= c.mod;
		}
	}

	int operator()(int n, int r) {
		int x = 0;
		int mod = 1;
		for (int i = 0; i < cs.size(); i++) {
			int y = cs[i](n, r);
			x += int64_t(y + cs[i].mod - x) * inv[i] % cs[i].mod * mod;
			mod *= cs[i].mod;
		}
		return x;
	}
};

int main() {
	int T;
	cin >> T;

	CombinationAnyMod cb(101010, 9);

	while (T--) {
		string s;
		cin >> s;

		int n = s.size();

		int ans = 0;
		for (int i = 0; i < n; i++) {
			(ans += cb(n - 1, i) * (s[i] - '0')) %= 9;
		}
		if (ans == 0) ans = 9;

		if (count(s.begin(), s.end(), '0') == n) ans = 0;
		printf("%d\n", ans);
	}
}