結果

問題 No.681 Fractal Gravity Glue
コンテスト
ユーザー chocorusk
提出日時 2018-12-09 23:54:26
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,939 bytes
コンパイル時間 1,185 ms
コンパイル使用メモリ 95,684 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-16 15:39:53
合計ジャッジ時間 1,636 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘ll solve(ll, ll)’:
main.cpp:68:1: warning: control reaches end of non-void function [-Wreturn-type]
   68 | }
      | ^

ソースコード

diff #
raw source code 

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD=1e9+7;
void matmul(ll a[3][3], ll b[3][3], ll ans[3][3]){
  for(int i=0; i<3; i++){
    for(int j=0; j<3; j++){
      ans[i][j]=0;
      for(int k=0; k<3; k++){
        ans[i][j]+=(a[i][k]*b[k][j]);
        ans[i][j]%=MOD;
      }
    }
  }
}
void matpow(ll a[3][3], ll k, ll ans[3][3]){
  ll ap[3][3];
  for(int i=0; i<3; i++){
    for(int j=0; j<3; j++){
      ap[i][j]=a[i][j], ans[i][j]=(i==j?1:0);
    }
  }
  while(k){
    ll ans1[3][3];
    if(k&1){
      matmul(ans, ap, ans1);
      for(int i=0; i<3; i++) for(int j=0; j<3; j++) ans[i][j]=ans1[i][j];
    }
    matmul(ap, ap, ans1);
    for(int i=0; i<3; i++) for(int j=0; j<3; j++) ap[i][j]=ans1[i][j];
    k>>=1;
  }
}
ll ct[101], w[101];
ll d;
ll total(ll b){
	if(b==1) return d;
	ll ans[3][3], a[3][3];
	a[0][0]=d+2, a[0][1]=(MOD-d-1), a[0][2]=d, a[1][0]=1, a[1][1]=0, a[1][2]=0, a[2][0]=0, a[2][1]=0, a[2][2]=1;
	matpow(a, b, ans);
	return (d*ans[1][0]+ans[1][2])%MOD;
}
ll solve(ll b, ll n){
	if(b==1) return n;
	for(ll i=1; i<=d+1; i++){
		if(n<=ct[b-1]*i+i-1){
			return (w[b-1]*(i-1)+b*(i-1)+solve(b-1, n-ct[b-1]*(i-1)-i+1))%MOD;
		}else if(n==ct[b-1]*i+i){
			return (w[b-1]*i+b*i)%MOD;
		}
	}
}
int main()
{
	ll n, b;
	cin>>n>>b>>d;
	if(b==1){
		cout<<d-n<<endl;
		return 0;
	}
	ct[1]=d;
	w[1]=d;
	int i1=-1;
	for(ll i=2; i<=100; i++){
		ct[i]=ct[i-1]*(d+1)+d;
		w[i]=(w[i-1]*(d+1)+i*d)%MOD;
		if(ct[i]>1e9){
			i1=i;
			break;
		}
	}
	for(int i=i1+1; i<=100; i++) ct[i]=ct[i-1];
	ll c;
	if(b>100) c=solve(100, n);
	else c=solve(b, n);
	cout<<(total(b)+MOD-c)%MOD<<endl;
	return 0;
}
0