結果

問題 No.720 行列のできるフィボナッチ数列道場 (2)
コンテスト
ユーザー 👑 testestest
提出日時 2018-07-29 00:40:15
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 727 bytes
コンパイル時間 251 ms
コンパイル使用メモリ 30,720 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-06 15:30:42
合計ジャッジ時間 1,099 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c:10:4: warning: conflicting types for built-in function 'pow'; expected 'double(double,  double)' [-Wbuiltin-declaration-mismatch]
   10 | r5 pow(r5 a,ll n){r5 x={1,0};for(;n;n/=2,a=mul(a,a))if(n&1)x=mul(x,a);return x;}
      |    ^~~
main.c:1:1: note: 'pow' is declared in header '<math.h>'
  +++ |+#include <math.h>
    1 | #define ll long long
main.c: In function 'main':
main.c:25:9: warning: implicit declaration of function 'scanf' [-Wimplicit-function-declaration]
   25 |         scanf("%lld%lld",&n,&m);
      |         ^~~~~
main.c:1:1: note: include '<stdio.h>' or provide a declaration of 'scanf'
  +++ |+#include <stdio.h>
    1 | #define ll long long
main.c:25:9: warning: incompatible implicit declaration of built-in function 'scanf' [-Wbuiltin-declaration-mismatch]
   25 |         scanf("%lld%lld",&n,&m);
      |         ^~~~~
main.c:25:9: note: include '<stdio.h>' or provide a declaration of 'scanf'
main.c:26:9: warning: implicit declaration of function 'printf' [-Wimplicit-function-declaration]
   26 |         printf("%lld",(f(phi,n,m)-f(varphi,n,m)+M+M)%M);
      |         ^~~~~~
main.c:26:9: note: include '<stdio.h>' or provide a declaration of 'printf'
main.c:26:9: warning: incompatible implicit declaration of built-in function 'printf' [-Wbuiltin-declaration-mismatch]
main.c:26:9: note: include '<stdio.h>' or provide a declaration of 'printf'

ソースコード

diff # 

#define ll long long
#define rep(i,l,r)for(ll i=l;i<r;i++)

#define M 1000000007
ll pom(ll a,ll n){ll x=1;for(a%=M;n;n/=2,a=a*a%M)if(n&1)x=x*a%M;return x;}
#define invp(a)pom(a,M-2)

typedef struct r5{ll a,b;}r5;
r5 mul(r5 x,r5 y){r5 z={(x.a*y.a+x.b*y.b*5)%M,(x.a*y.b+x.b*y.a)%M};return z;}
r5 pow(r5 a,ll n){r5 x={1,0};for(;n;n/=2,a=mul(a,a))if(n&1)x=mul(x,a);return x;}
r5 inv(r5 x){ll d=invp(x.a*x.a-5*x.b*x.b);x.a=x.a*d%M;x.b=-x.b*d%M;return x;}

ll f(r5 x,ll n,ll m){
	r5 t1=pow(x,n*m);
	t1.a--;
	r5 t2=pow(x,m);
	t2.a--;
	return mul(pow(x,m),mul(t1,inv(t2))).b;
}

int main(){
	r5 phi={(M+1)/2,(M+1)/2};
	r5 varphi={(M+1)/2,-(M+1)/2};
	ll n,m;
	scanf("%lld%lld",&n,&m);
	printf("%lld",(f(phi,n,m)-f(varphi,n,m)+M+M)%M);
}
0