結果

問題 No.435 占い(Extra)
コンテスト
ユーザー kwm_t
提出日時 2026-06-14 12:41:41
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
MLE  
実行時間 -
コード長 2,938 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,816 ms
コンパイル使用メモリ 334,640 KB
実行使用メモリ 159,616 KB
最終ジャッジ日時 2026-06-14 12:41:56
合計ジャッジ時間 12,642 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample MLE * 4
other MLE * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
// using namespace atcoder;
// using mint = modint1000000007;
// const int mod = 1000000007;
// using mint = modint998244353;
// const int mod = 998244353;
// const int INF = 1e9;
// const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rrep(i, n) for (int i = (n)-1; i >= 0; --i)
#define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define P pair<int, int>
template<typename A, typename B> inline bool chmax(A &a, const B &b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A &a, const B &b) { if (a > b) { a = b; return true; } return false; }

#ifndef KWM_T_MATH_BINOM_MOD9_HPP
#define KWM_T_MATH_BINOM_MOD9_HPP

#include <vector>
#include <cassert>

namespace kwm_t::math {

struct BinomMod9 {
	static constexpr int MOD = 9;

	int max_n;

	// fact[i] = i! から 3 を除いた部分 (mod 9)
	std::vector<int> fact;

	// 逆元
	std::vector<int> ifact;

	// v3(i!)
	std::vector<int> cnt3;

	// 3^k mod 9
	std::vector<int> pow3;

	static int mod_pow(int a, long long e) {
		int r = 1;
		while (e) {
			if (e & 1) r = r * a % MOD;
			a = a * a % MOD;
			e >>= 1;
		}
		return r;
	}

	static int inv_mod9(int x) {
		// mod 9 で逆元を持つのは
		// 1,2,4,5,7,8
		return mod_pow(x, 5); // φ(9)=6
	}

	explicit BinomMod9(int N)
		: max_n(N),
		fact(N + 1),
		ifact(N + 1),
		cnt3(N + 1),
		pow3(N + 1)
	{
		fact[0] = 1;
		cnt3[0] = 0;

		for (int i = 1; i <= N; i++) {
			int x = i;
			int c = 0;

			while (x % 3 == 0) {
				x /= 3;
				++c;
			}

			fact[i] = fact[i - 1] * (x % MOD) % MOD;
			cnt3[i] = cnt3[i - 1] + c;
		}

		ifact[N] = inv_mod9(fact[N]);

		for (int i = N; i >= 1; i--) {
			int x = i;
			while (x % 3 == 0) x /= 3;

			ifact[i - 1] = ifact[i] * (x % MOD) % MOD;
		}

		pow3[0] = 1;
		for (int i = 1; i <= N; i++) {
			pow3[i] = pow3[i - 1] * 3 % MOD;
		}
	}

	int C(int n, int k) const {
		if (k < 0 || k > n) return 0;

		int e =
			cnt3[n]
			- cnt3[k]
			- cnt3[n - k];

		if (e >= 2) return 0;

		int res = fact[n];

		res = res * ifact[k] % MOD;
		res = res * ifact[n - k] % MOD;

		if (e == 1) res = res * 3 % MOD;

		return res;
	}

	int operator()(int n, int k) const {
		return C(n, k);
	}
};

} // namespace kwm_t::math

#endif


int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	kwm_t::math::BinomMod9 comb(10000007);
	int t; cin >> t;
	while (t--) {
		int n, x, a, b, m;
		cin >> n >> x >> a >> b >> m;
		long long r = x;
		int ans = 0;
		long long sum = 0;
		rep(i, n) {
			if (i != 0) {
				r = ((r^a) + b) % m;
			}
			sum += r;
			auto rr = r % 10;
			ans += comb.C(n - 1, i) *rr;
			ans %= 9;
		}
		if (ans == 0 && sum != 0)ans = 9;
		cout << ans << endl;
	}
	return 0;
}
0