メモ

yukicoderでゆるふわgolf

yukicoder No.557 点対称

問題はこちら
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