結果

問題 No.435 占い(Extra)
ユーザー te-shte-sh
提出日時 2017-12-19 17:21:42
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 1,346 ms / 2,000 ms
コード長 3,870 bytes
コンパイル時間 991 ms
コンパイル使用メモリ 103,364 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-12 23:13:34
合計ジャッジ時間 22,668 ms
ジャッジサーバーID
(参考情報)
judge1 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import std.algorithm, std.conv, std.range, std.stdio, std.string;
import std.typecons; // Tuple, Nullable, BigFlags
alias mint = FactorRing!9;
void main()
{
auto t = readln.chomp.to!int;
auto f3 = new int[](16);
f3[0] = 1;
foreach (i; 1..16) f3[i] = f3[i-1]*3;
auto f3m = new mint[](16);
foreach (i; 0..16) f3m[i] = mint(f3[i], true);
auto split3(int i)
{
auto j = 0;
while (i > 0 && i%3 == 0) {
++j;
i /= 3;
}
return tuple(j, mint(i, true));
}
foreach (_; 0..t) {
auto rd = readln.splitter;
auto n = rd.front.to!int; rd.popFront();
auto x = rd.front.to!int; rd.popFront();
auto a = rd.front.to!int; rd.popFront();
auto b = rd.front.to!int; rd.popFront();
auto m = rd.front.to!int;
auto ans = mint(0), s = 0;
auto r = x;
auto c3 = 0, co = mint(1);
foreach (i; 0..n) {
ans += mint(r%10, true) * f3m[c3] * co;
s += r%10;
auto r1 = split3(n-i-1), r2 = split3(i+1);
c3 += r1[0] - r2[0];
co *= r1[1] / r2[1];
r = ((r ^ a) + b) % m;
}
if (s == 0)
writeln(0);
else
writeln(ans == 0 ? 9 : ans);
}
}
struct FactorRing(int m, bool pos = false)
{
version(BigEndian) {
union { long vl; struct { int vi2; int vi; } }
} else {
union { long vl; int vi; }
}
static init() { return FactorRing!(m, pos)(0); }
@property int toInt() { return vi; }
alias toInt this;
this(int v) { vi = v; }
this(int v, bool runMod) { vi = runMod ? mod(v) : v; }
this(long v) { vi = mod(v); }
ref FactorRing!(m, pos) opAssign(int v) { vi = v; return this; }
pure auto mod(int v) const
{
static if (pos) return v % m;
else return (v % m + m) % m;
}
pure auto mod(long v) const
{
static if (pos) return cast(int)(v % m);
else return cast(int)((v % m + m) % m);
}
static if (!pos) {
pure auto opUnary(string op: "-")() const { return FactorRing!(m, pos)(mod(-vi)); }
}
static if (m < int.max / 2) {
pure auto opBinary(string op: "+")(int rhs) const { return FactorRing!(m, pos)(mod(vi + rhs)); }
pure auto opBinary(string op: "-")(int rhs) const { return FactorRing!(m, pos)(mod(vi - rhs)); }
} else {
pure auto opBinary(string op: "+")(int rhs) const { return FactorRing!(m, pos)(mod(vl + rhs)); }
pure auto opBinary(string op: "-")(int rhs) const { return FactorRing!(m, pos)(mod(vl - rhs)); }
}
pure auto opBinary(string op: "*")(int rhs) const { return FactorRing!(m, pos)(mod(vl * rhs)); }
pure auto opBinary(string op)(FactorRing!(m, pos) rhs) const
if (op == "+" || op == "-" || op == "*") { return opBinary!op(rhs.vi); }
static if (m < int.max / 2) {
auto opOpAssign(string op: "+")(int rhs) { vi = mod(vi + rhs); }
auto opOpAssign(string op: "-")(int rhs) { vi = mod(vi - rhs); }
} else {
auto opOpAssign(string op: "+")(int rhs) { vi = mod(vl + rhs); }
auto opOpAssign(string op: "-")(int rhs) { vi = mod(vl - rhs); }
}
auto opOpAssign(string op: "*")(int rhs) { vi = mod(vl * rhs); }
auto opOpAssign(string op)(FactorRing!(m, pos) rhs)
if (op == "+" || op == "-" || op == "*") { return opOpAssign!op(rhs.vi); }
pure auto opBinary(string op: "/")(FactorRing!(m, pos) rhs) { return FactorRing!(m, pos)(mod(vl * rhs.inv.vi)); }
pure auto opBinary(string op: "/")(int rhs) { return opBinary!op(FactorRing!(m, pos)(rhs)); }
auto opOpAssign(string op: "/")(FactorRing!(m, pos) rhs) { vi = mod(vl * rhs.inv.vi); }
auto opOpAssign(string op: "/")(int rhs) { return opOpAssign!op(FactorRing!(m, pos)(rhs)); }
pure auto inv() const
{
int x = vi, a, b;
exEuclid(x, m, a, b);
return FactorRing!(m, pos)(mod(a));
}
}
pure T exEuclid(T)(T a, T b, ref T x, ref T y)
{
auto g = a;
x = 1;
y = 0;
if (b != 0) {
g = exEuclid(b, a % b, y, x);
y -= a / b * x;
}
return g;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0