メモ

yukicoderでゆるふわgolf

yukicoder No.492 IOI数列

問題はこちら
No.492 IOI数列 - yukicoder

mod 101010101010101010101の方は睨むと周期性がわかる(頭のなかで筆算を思い浮かべてみる)

anは初項1公比100の等比数列の第n項までの和なので、和の公式からa_n=\frac{100^n-1}{99}になっていることがわかる
ということで繰り返し二乗法によりmod 10^9+7の場合もわかる

#define ll long long
#define invp(a,p)pom(a,p-2,p)
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;}

m=1e9+7;
long s,n;
main(){
	scanf("%ld",&n);
	printf("%d\n",(pom(100,n,m)-1)*invp(99,m)%m);
	for(int i=n%11;i;i--)s=s*100+1;
	printf("%d",s);
}

pomの第二引数がlongじゃないとダメなので引数が省略できないことに注意しつつ(1WA)、ぎゅっとする

P=1e9+7;
long s,x,n;
p(long a,long i){x=i?p(a*a%P,i/2),i%2?x*a%P:x:1;}

main(){
	for(scanf("%ld",&n),p(100,n);n--%11;s=s*100+1);
	printf("%d\n%ld",646464651*~-x%P,s);
}

159B


2017/08/12追記

フェルマーの小定理から、指数はP-1での剰余で考えればよく、これによりpの引数の型名が省略できる
P=1e9+7;
long s,x,n;
p(a,i){x=i?p(1L*a*a%P,i/2),i%2?x*a%P:x:1;}
main(){
	for(scanf("%ld",&n),p(100,n%~-P);n--%11;s=s*100+1);
	printf("%d\n%ld",646464651*~-x%P,s);
}