yukicoder : No.493 とても長い数列と文字列(Long Long Sequence and a String）

なんか今回入力がシンプルな問題が多いな。
http://yukicoder.me/problems/no/493

問題

以下のように定義される文字列f(n)を考える。

• f(1) = "1"
• f(n) = f(n-1) + (n*nを文字列化したもの) + f(n-1)

整数K,L,Rが与えられる。
f(K)のうちL文字目～R文字目の数字の和および積(の(10^9+7)の剰余)を求めよ。
ただし'0'は和・積の演算においては10とみなすものとする。

なお、Rがf(K)を超える場合は-1を答えよ。

解法

f(K)における先頭R文字の和・積を求め、f(K)における先頭L文字の和・積を求めで、前者から後者を引く・割れば解が求められる。
よって、以下はf(K)の先頭V文字の和・積の求め方を考えよう。

まず以下を考えよう。(以後、'0'を10とみなすことや10^9+7の剰余は省略)

• L(n) := |f(n)|
• S(n) := f(n)の各桁の和
• P(n) := f(n)の各桁の積

f(n)がf(n-1)から求められることを考えると、これらもL(n-1),S(n-1),P(n-1)から容易に求められる。

f(60)程度まで求めると、この時点でL(60)が10^18を超えることがわかる。
よってKが大きくても実際はKが60以下まで考えればよい。
また、L(K)がわかるので「Rがf(K)を超える場合は-1を答えよ。」はこの時点で判定できる。

上記を使ってf(K)の先頭V文字の和・積の求め方を考えよう。
g(K,V) := f(K)の先頭V文字の和・積

上記値は以下の通り求められる。

• V==0なら和=0、積=1
• V≦L(K-1)ならg(K-1,V)を答える。
• V≦L(K-1)+(K*Kを文字列化したもの)なら、S(K-1)、P(K-1)に対し(K*Kを文字列化したもの)の先頭(V-L(K-1))文字分を加える・掛け合わせればよい。
• V＞L(K-1)+(K*Kを文字列化したもの)なら、S(K-1)、P(K-1)に対し(K*Kを文字列化したもの)の文字分を加える・掛け合わせ、さらにg(K-1,V-L(K-1)+(K*Kを文字列化したもの))の値を加える・掛け合わせればよい。

int K;
ll L,R;
ll F[100],S[100],P[100];
ll mo=1000000007;

string ST[100];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

pair<ll,ll> getval(int K,ll V) {
	if(V<=0) return {0,1};
	
	if(V==F[K]) return {S[K],P[K]};
	if(V<=F[K-1]) return getval(K-1,V);
	
	ll sum=S[K-1],prod=P[K-1];
	V -= F[K-1];
	
	ll i;
	FOR(i,min(V,(ll)ST[K].size())) {
		sum += ST[K][i];
		(prod *= ST[K][i])%=mo;
	}
	
	auto r=getval(K-1,V-ST[K].size());
	sum += r.first;
	(prod *= r.second)%=mo;
	return {sum,prod};
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	F[1]=S[1]=P[1]=1;
	ST[1]="1";
	ST[1][0]-='0';
	for(i=2;i<=61;i++) {
		F[i]=2*F[i-1];
		S[i]=2*S[i-1];
		P[i]=P[i-1]*P[i-1]%mo;
		
		char buf[20];
		sprintf(buf,"%d",i*i);
		ST[i]=buf;
		FORR(c,ST[i]) {
			c-='0';
			if(c==0) c+=10;
			F[i]++;
			S[i]+=c;
			P[i]=P[i]*c%mo;
		}
	}
	
	cin>>K>>L>>R;
	K=min(K,60);
	if(R>F[K]) return _P("-1\n");
	
	auto RR = getval(60,R);
	auto LL = getval(60,L-1);
	cout<<RR.first-LL.first<<" "<<RR.second*modpow(LL.second)%mo<<endl;
	
}

まとめ

なんで英語の問題名がついているんだろう？