結果
問題 |
No.720 行列のできるフィボナッチ数列道場 (2)
|
ユーザー |
👑 ![]() |
提出日時 | 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'
ソースコード
#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); }