問題はこちら
No.557 点対称 - yukicoder
回文と同様、上半分を決めると下半分は自動的に決まる
・n=1のとき
1,8の2通り
・nが偶数のとき
上位n/2桁を決めると、下位は自動的に決まる
先頭の位に使えるのは1,6,8,9の4通り
それ以外は0,1,6,8,9の5通り
よって4*5^(n/2-1)
・nが3以上の奇数のとき
上位(n+1)/2桁を決めると、下位は自動的に決まる
先頭の位に使えるのは1,6,8,9の4通り
真ん中の位に使えるのは0,1,8の3通り
それ以外は0,1,6,8,9の5通り
よって4*3*5^((n+1)/2-2)
冪剰余は繰り返し二乗法により求める
#define ll long long ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n%2?x=x*a%m:0,a=a*a%m;return x;} ll n,m=1e9+7,ans; main(){ scanf("%ld",&n); if(n==1)ans=2; else if(n%2==0)ans=4*pom(5,n/2-1,m)%m; else ans=12*pom(5,(n+1)/2-2,m)%m; printf("%d",ans); }
整数除算は切り捨てられることから、5の指数部分はn/2-1とまとめられる
繰り返し二乗法の実装をぎゅっとするなどして(c.f.yukicoder No.117 組み合わせの数 - メモ)
long x,n; m=1e9+7; p(a,i){x=i?p(1L*a*a%m,i/2),i%2?x*a%m:x:1;} main(){ scanf("%ld",&n); p(5,(n/2-1)%~-m);//フェルマーの小定理 printf("%d",n>1?(n%2*8+4)*x%m:2); }
133B