CF628B New Skateboard 题解

2024-09-02 12:36:15

Content

有一个长度为 \(n\) 的数字串 \(s\)，求出有多少个子串能够被 \(4\) 整除。

数据范围：\(1\leqslant n\leqslant 3\times 10^5\)。

Solution

众所周知，如果最后两位数能够被 \(4\) 整除，这个数也能够被 \(4\) 整除，所以我们只需要看最能被 \(4\) 整除的长度为 \(1\) 或者 \(2\) 的子串有多少个就好。

设能被 \(4\) 整除的长度为 \(1\) 的子串的个数是 \(n_1\)，能被 \(4\) 整除的长度为 \(2\) 的子串的个数是 \(n_2\) 且第 \(i\) 个子串的最高位在原串的位置是 \(p_i\)，答案就是 \(\sum\limits_{i=1}^{n_2}p_i+n_1\)。

Code

string s;

long long ans;

int main() {

	//This program is written in Windows 10 by Eason_AC

	cin >> s;

	int len = s.size();

	_for(i, 0, len - 1) {

		if(!((s[i] - '0' + (s[i - 1] - '0') * 10) % 4)) ans += i;

		if(!((s[i] - '0') % 4))	ans++;

	}

	writell(ans);

	return 0;

}

最新文章

热门文章