結果

問題 No.344 ある無理数の累乗
コンテスト
ユーザー r_dream0
提出日時 2017-02-22 21:52:28
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,009 bytes
コンパイル時間 921 ms
コンパイル使用メモリ 72,896 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-30 19:24:58
合計ジャッジ時間 2,164 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
using namespace std;
// (1+sqrt(3)) ^ n + (1 - sqrt(3)) ^ nは次のような数列になる
// 2, 2, 8, 20, 56, 152, ... f(n+2)=2(f(n + 1) + f(n))
// (1 - sqrt(3)) ^ n < 1より上の数列の値-1が求める整数
// 
const int64_t MOD = 1000;
void next(vector<long> &x, const vector<long> &first, long MOD) {
  long last = x.back();
  for(int i = x.size() - 2;  i >= 0 ; i--) x[i + 1] = x[i];
  x[0] = 0;
  for(int i = 0; i < x.size(); i++) x[i] = (MOD + x[i] - (long)last * first[i] % MOD) % MOD;
}

vector<long> next2N(const vector<long> &x, const vector<long> &first, long MOD) {
  vector<long> tmp(x);
  vector<long> result(x.size());
  for(int i = 0; i < x.size(); i++) {
    for(int j = 0; j < tmp.size(); j++) {
      result[j] = (result[j] + MOD - x[i] * tmp[j]) % MOD;
    }
    next(tmp, first, MOD);
  }
  return result;
}
long calc(const vector<long> &poly, const vector<long> &x, long MOD, int ofs = 0) {
  __int128_t ret = 0;
  for(int i = 0; i < poly.size(); i++) {
    ret += x[i + ofs] * poly[i] % MOD;
    ret %= MOD;
  }
  return (MOD - ret) % MOD;
}
long kitamasa(const vector<long> &poly, const vector<long> &x, int64_t N, long MOD) {
  if(N < poly.size()) return x[N];
  int t = poly.size(), l = 0;
  while(t > 0) t >>= 1, l++;
  for(int i = 0; i <= l; i++) {
    if(N >> (63 - __builtin_clzl(N) - l + i) & 1) {
      t |= 1LL << i;
    }
  }
  long cur = poly.size();
  vector<long> curPoly = poly;
  vector<long> poy2 = poly;
  while(cur < t) {
    if(cur == N) {
      return calc(curPoly, x, MOD);
    }
    next(curPoly, poly, MOD);
    cur++;
  }
  vector<long> ret(curPoly.size());
  cur = 0;
  for(int i = 63 - __builtin_clzl(N) - l - 1; i >= 0; i--) {
    curPoly = next2N(curPoly, poly, MOD);
    if(N >> i & 1) next(curPoly, poly, MOD);
  }
  return calc(curPoly, x, MOD);
}

int main() {
  int n;
  cin >> n;
  vector<int64_t> poly(2, -2);
  vector<int64_t> iv(2, 2);
  cout << (kitamasa(poly, iv, n, MOD) + MOD - 1) % MOD << endl;
}
0