結果
| 問題 |
No.303 割れません
|
| ユーザー |
 te-sh
|
| 提出日時 | 2017-06-15 11:23:16 |
| 言語 | D (dmd 2.109.1) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 6,088 bytes |
| コンパイル時間 | 1,561 ms |
| コンパイル使用メモリ | 141,076 KB |
| 実行使用メモリ | 14,512 KB |
| 最終ジャッジ日時 | 2024-06-12 20:04:15 |
| 合計ジャッジ時間 | 11,301 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 2 RE * 12 |
ソースコード
import std.algorithm, std.conv, std.range, std.stdio, std.string;
alias BigInt2!9 Bi;
void main()
{
auto l = readln.chomp.to!int;
if (l == 1) {
writeln(1);
writeln(1);
} else if (l == 2) {
writeln(3);
writeln("INF");
} else {
writeln(l);
auto r = calc(l);
if (l % 2 == 0) {
auto s = calc(l/2);
writeln((r - s * s).toString);
} else {
writeln(r.toString);
}
}
}
auto calc(int l)
{
auto o = Bi(1), z = Bi(0);
auto a = [[o,o],[o,z]];
auto im = [[o,z],[z,o]];
auto b = repeatedSquare!(Bi[][], matMul)(a, l-2, im);
return b[0][0] + b[0][1];
}
T[][] matMul(T)(T[][] a, T[][] b)
{
auto l = b.length, m = a.length, n = b[0].length;
auto c = new T[][](m, n);
foreach (i; 0..m)
foreach (j; 0..n)
foreach (k; 0..l)
c[i][j] += a[i][k] * b[k][j];
return c;
}
T[] matMulVec(T)(T[][] a, T[] b)
{
auto l = b.length, m = a.length;
auto c = new T[](m);
foreach (i; 0..m)
foreach (j; 0..l)
c[i] += a[i][j] * b[j];
return c;
}
T repeatedSquare(T, alias pred = "a * b", U)(T a, U n, T init)
{
import std.functional;
alias predFun = binaryFun!pred;
if (n == 0) return init;
static buf = new T[](32);
static bufFilled = 0;
if (bufFilled == 0)
buf[bufFilled++] = a;
auto r = init, i = 0;
while (n > 0) {
if ((n & 1) == 1)
r = predFun(r, buf[i]);
if (++i == bufFilled)
buf[bufFilled++] = predFun(buf[i-1], buf[i-1]);
n >>= 1;
}
return r;
}
struct BigInt2(long w = 9)
{
import std.algorithm, std.array, std.conv, std.range, std.string;
const base = 10 ^^ w;
int[] z;
int sign = 1;
this(long v)
{
if (v < 0) { sign = -1; v = -v; }
for (; v > 0; v /= base) z ~= (v % base).to!int;
}
this(int[] z, int sign)
{
this.z = z;
this.sign = sign;
}
pure auto dup() const
{
return BigInt2!w(z.dup, sign);
}
pure auto opCmp(const BigInt2!w v) const
{
if (sign != v.sign)
return sign < v.sign ? -1 : 1;
if (z.length != v.z.length)
return z.length * sign < v.z.length * v.sign ? -1 : 1;
foreach_reverse (i; 0..z.length)
if (z[i] != v.z[i])
return z[i] < v.z[i] ? -sign : sign;
return 0;
}
pure auto toString()
{
auto ap = appender!string();
if (z.empty) {
ap.put("0");
return ap.data;
}
if (sign == -1) ap.put("-");
ap.put(format("%d", z[$-1]));
auto fmt = "%0" ~ w.to!string ~ "d";
foreach_reverse (zi; z[0..$-1]) ap.put(format(fmt, zi));
return ap.data;
}
pure auto opUnary(string op: "-")() const
{
auto res = dup;
if (!z.empty) res.sign = -sign;
return res;
}
pure auto opBinary(string op: "+")(const BigInt2!w v) const
{
if (v.z.empty) return dup;
if (sign == v.sign) {
auto res = v.dup;
for (int i = 0, carry = 0; i < max(z.length, v.z.length) || carry; ++i) {
if (i == res.z.length)
res.z ~= 0;
res.z[i] += carry + (i < z.length ? z[i] : 0);
carry = res.z[i] >= base;
if (carry) res.z[i] -= base;
}
return res;
}
return this - (-v);
}
pure auto opBinary(string op: "-")(const BigInt2!w v) const
{
if (v.z.empty) return dup;
if (sign == v.sign) {
if (sign == 1 && this >= v || sign == -1 && this <= v) {
auto res = dup;
for (int i = 0, carry = 0; i < v.z.length || carry; ++i) {
res.z[i] -= carry + (i < v.z.length ? v.z[i] : 0);
carry = res.z[i] < 0;
if (carry) res.z[i] += base;
}
res.trim();
return res;
}
return -(v - this);
}
return this + (-v);
}
pure auto opBinary(string op: "*")(const BigInt2!w v) const
{
if (z.empty || v.z.empty) return BigInt2!w(0);
auto a6 = convertBase(z, w, 6);
auto b6 = convertBase(v.z, w, 6);
auto a = a6.to!(long[]), b = b6.to!(long[]);
while (a.length < b.length) a ~= 0L;
while (b.length < a.length) b ~= 0L;
while (a.length & (a.length - 1)) { a ~= 0L; b ~= 0L; }
auto c = karatsuba(a, b);
BigInt2!w res;
res.sign = sign * v.sign;
for (int i = 0, carry = 0; i < c.length; ++i) {
auto cur = c[i] + carry;
res.z ~= (cur % 1000000).to!int;
carry = (cur / 1000000).to!int;
}
res.z = convertBase(res.z, 6, w);
res.trim();
return res;
}
pure int[] convertBase(const int[] a, int oldDigits, int newDigits) const
{
auto p = new long[](max(oldDigits, newDigits) + 1);
p[0] = 1;
foreach (i; 1..p.length) p[i] = p[i-1] * 10;
int[] res;
long cur = 0;
int curDigits = 0;
foreach (i; 0..a.length) {
cur += a[i] * p[curDigits];
curDigits += oldDigits;
while (curDigits >= newDigits) {
res ~= (cur % p[newDigits]).to!int;
cur /= p[newDigits];
curDigits -= newDigits;
}
}
res ~= cur.to!int;
while (!res.empty && res[$-1] == 0) res = res[0..$-1];
return res;
}
pure long[] karatsuba(const long[] a, const long[] b) const
{
auto n = a.length;
auto res = new long[](n * 2);
if (n <= 32) {
foreach (i; 0..n)
foreach (j; 0..n)
res[i+j] += a[i] * b[j];
return res;
}
auto k = n >> 1;
auto a1 = a[0..k].dup, a2 = a[k..$].dup;
auto b1 = b[0..k].dup, b2 = b[k..$].dup;
auto a1b1 = karatsuba(a1, b1);
auto a2b2 = karatsuba(a2, b2);
foreach (i; 0..k) a2[i] += a1[i];
foreach (i; 0..k) b2[i] += b1[i];
auto r = karatsuba(a2, b2);
foreach (i; 0..a1b1.length) r[i] -= a1b1[i];
foreach (i; 0..a2b2.length) r[i] -= a2b2[i];
foreach (i; 0..r.length) res[i+k] += r[i];
foreach (i; 0..a1b1.length) res[i] += a1b1[i];
foreach (i; 0..a2b2.length) res[i+n] += a2b2[i];
return res;
}
auto opOpAssign(string op)(const BigInt2!w v)
if (op == "+" || op == "-" || op == "*")
{
auto res = opBinary!op(v);
z = res.z;
sign = res.sign;
return this;
}
auto trim()
{
while (!z.empty && z[$-1] == 0) z = z[0..$-1];
if (z.empty) sign = 1;
}
}