2023 江苏省赛

题目链接

B

对于 \(n\) 对关系 , 反过来考虑 \(b_{i} > b{i + 1}\)的个数

观察 \(bn\) 的形式 :

\(x ,\ x + a_{0} ,\ x + a_{0} + a_{1} \ ,\ .... ,\ x + a_{0} + ... + a_{n - 1}\)

其中 \(x,a_{i}\)均为模 \(m\) 后数 , 相当把外层取模内置(一定要算取模后的，不然后面的证明不成立)

那么可以想到一段成为 \(m\) 上如果 \(b_{i} = x + a_{0} + ... + a_{i - 1} < m\) , \(b_{i+1} = x + a_{0} + ... + a_{i}\) > m , 那么 \(b_{i}\) 一定在取模意义下大于 \(b_{i+1}\) ( $b_{i} + a_{i} > m $ 等价于 \(b_{i} > m - a_{i}\) , \(m - a_{i}\) 就是 \(b_{i}\) 对 m 取模) , 计算这样出现的次数即可 (\(b_{i+1}\)大于\(m\)说明到了下一段 \(m\)) , 计算这样出现的次数即可

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
	
	int k;
	cin >> k;
	vector<ll> a(k);
	for(int i = 0 ; i < k ; ++i)
		cin >> a[i];
	
	ll n,m,x;
	cin >> n >> m >> x;
	
	ll sum = 0;
	for(int i = 0 ; i < k ; ++i) {
		sum += a[i] % m;
	}
	
	ll bn = sum * (n / k) + x % m;

	int pos = n % k;
	for(int i = 0 ; i < pos ; ++i)
		bn += a[i] % m;
		
	cout << n - bn / m << '\n';
	
	return 0;
}