yukicoder : No.2905 Nabeatsu Integration

ナベアツ感あるのサンプルだけ…？
https://yukicoder.me/problems/no/2905

問題

数字からなる文字列Sが与えられる。
0以上1未満のxに対し、f(x)は、xの小数表記中にSが現れるとき、最初に現れる位置(小数点i桁目から|S|文字がSと一致するなら、i)とする。

f(x)をx=0から1まで積分したときの値を求めよ。

解法

Sの先頭k文字と末尾k文字が一致するとき、10^kが解に計上されるらしい。
なので、Zalgorithmでそのような判定をすればよい。

KMP法とかの要領で、愚直に一致桁数の状態遷移を求めても解けるようす。

int N;
string S;

using VT = string;

vector<int> Zalgo(VT s) {
	vector<int> v(1,s.size());
	for(int i=1,l=-1,r=-1;i<s.size();i++) {
		if(i<=r && v[i-l]<r-i+1) v.push_back(v[i-l]);
		else {
			l=i; r=(i>r)?i:(r+1);
			while(r<s.size() && s[r-i]==s[r]) r++;
			v.push_back((r--)-l);
		}
	}
	v.push_back(0);
	return v;
}
const ll mo=998244353;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	ll ret=0;
	auto Z=Zalgo(S);
	ll p=1;
	for(i=1;i<=N;i++) {
		p=p*10%mo;
		if(Z[N-i]>=i) ret+=p;
	}
	ret+=mo-(N-1);
	cout<<ret%mo<<endl;
}

まとめ

後者はともかく、前者は思いつかなかったな…。