結果

問題 No.681 Fractal Gravity Glue
コンテスト
ユーザー fuppy_kyopro
提出日時 2018-04-28 02:18:26
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 3,219 bytes
コンパイル時間 1,488 ms
コンパイル使用メモリ 172,632 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-27 23:12:22
合計ジャッジ時間 2,220 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
 
#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl
 
typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define in(x, a, b) a <= x && x < b
const int inf = 1000000001;
const ll INF = 2e18;
const ll MOD = 1000000007;
//const ll mod = 1000000009;
const double pi = 3.14159265358979323846;
#define Sp(p) cout<<setprecision(15)<< fixed<<p <<endl;
int dx[4] = { 1,0, -1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };


typedef vector<ll> vec;
typedef vector<vec> mat;

mat mul(mat &A, mat &B) {
  mat C(A.size(), vec(B[0].size()));
  bool flag = false;
  for (int i = 0; i < A.size(); i++) {
    for (int k = 0; k < B.size(); k++) {
      for (int j = 0; j < B[0].size(); j++) {
	C[i][j] = C[i][j] + A[i][k] * B[k][j];
	if (i == 1) {
	  if (C[i][j] >= MOD) {
	    flag = true;
	  }
	}
	C[i][j] %= MOD;
      }
    }
  }
  if (flag) {
    rep (k, C[1].size()) {
      C[1][k] = 0;
    }
  }
  flag = true;
  rep (i, 4) {
    if (A[1][i] + B[1][i] != 0) {
      flag = false;
    }
  }
  if (flag) {
    rep (k, C[1].size()) {
      C[1][k] = 0;
    }
  }
  return C;
}

vec mul(mat &A, vec &B) {
  vec C(A.size());
  bool flag = false;
  for (int i = 0; i < A.size(); i++) {
    for (int j = 0; j < B.size(); j++) {
      C[i] += A[i][j] * B[j];
      if (i == 1 && C[i] >= MOD) {
	C[i] = 0;
      }
      else {
	C[i] %= MOD;
      }
    }
  }
  return C;
}


mat pow(mat A, ll n) {
  mat B(A.size(), vec(A.size()));
  for (int i = 0; i < A.size(); i++) {
    B[i][i] = 1;
  }
  while (n > 0) {
    if (n & 1)B = mul(A, B);
    A = mul(A, A);
    n >>= 1;
  }
  return B;
}


int main() {
  ll n,b,d;
  cin >> n >> b >> d;
  mat A = {{d + 1, 0, d, d},
	   {0, d + 1, 0, d},
	   {0, 0, 1, 1},
	   {0, 0, 0, 1}};
  vec x1 = {d, d, 1, 1};

  mat Ab = pow(A, b - 1);
  vec xb = mul(Ab, x1);
  ll allsize = xb[0];
  int i = 0;
  vector<pll> numsize;
  while (true) {
    mat A2 = pow(A, i);
    vec x = mul(A2, x1);
    //DEBUG_VEC(x);
    if (x[1] == 0) {
      break;
    }
    numsize.push_back(pll(x[1], x[0]));
    i++;
  }
  //DEBUG(allsize);
  /*
  rep (i, numsize.size()) {
    cout << numsize[i].first << " " << numsize[i].second << endl;
  }
  //*/
  ll now = 0;
  for (int i = numsize.size() - 1; i >= 0; i--) {
    if (n == numsize[i].first) {
      now += numsize[i].second;
      now %= MOD;
      break;
    }
    ll num = numsize[i].first + 1, sz = (numsize[i].second + (i + 2)) % MOD;
    ll kosuu = n / num;
    if (kosuu == d + 1) {
      kosuu--;
    }
    now += kosuu * sz % MOD;
    now %= MOD;
    n -= num * kosuu;
    //DEBUG(i);
    //DEBUG(now);
    //DEBUG(n);
  }
  now += n;
  now %= MOD;
  cout << (allsize - now + 3*MOD) % MOD << endl;
}
0