[简单思维] 题解 Modularness

[简单思维] 题解 Modularness

题目链接

题目分析

构造一个序列 (b) ，其中第 (1) 个数是 (x) ，接下来就是 (d_0,d_1,dots,d_{k-1}) 不断重复：

[x,d_0,d_1,dots,d_{k-1},d_0,d_1,dots,d_{k-1},d_0,dots ]

那么序列 (a) 就是序列 (b) 前 (n) 项的前缀和，不妨假设 (0le x,d_0,d_1,dots,d_{k-1}<m) ，考虑何时有 ((a_jmod m)<(a_{j+1}mod m)) ，当且仅当 ((a_jmod m)+b_{j+1}<m) 并且 (b_{j+1} e 0) ，考虑会有多少个 (j) 满足这个条件，由于序列 (b) 中每个数都小于 (m) ，所以序列 (a) 除以 (m) 向下取整得到的非负整数将是连续的从 (0) 一直到 (lfloorfrac{a_n}{m} floor) （类似 (0,0,dots,0,0,1,1,dots,1,1,2,2,dots,2,2,3,3,dots,dots,lfloorfrac{a_n}{m} floor) ），如果 (lfloorfrac{a_j}{m} floor<lfloorfrac{a_{j+1}}{m} floor) ，那么说明 ((a_jmod m)+b_{j+1}ge m) ，也就是说，序列 (a) 除以 (m) 向下取整得到的结果中每次加一就有一个不满足 ((a_jmod m)+b_{j+1}<m) ，所以有 (lfloorfrac{a_n}{m} floor) 个数不满足条件，另外如果 (b_{j+1}=0) 时也不满足条件，此时我们就得到了有多少个 (j) 满足 ((a_jmod m)<(a_{j+1}mod m)) 。

时间复杂度 (mathcal O(qk)) 。

参考代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;
template<typename T>void read(T&x){
	static char c;static int f;
	for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
	for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
	static char q[65];int cnt=0;
	if(x<0)pc('-'),x=-x;
	q[++cnt]=x%10,x/=10;
	while(x)
		q[++cnt]=x%10,x/=10;
	while(cnt)pc(q[cnt--]+'0');
}
const int maxk=5005;
int d[maxk];
int main(){
	int k,q;read(k),read(q);
	for(int i=0;i<k;++i)read(d[i]);
	while(q--){
		int n,x,m;
		read(n),read(x),read(m);--n;
		int ndk=n/k,nmk=n%k;
		long long sum=x%m;int cnt=0;
		for(int i=0;i<k;++i){
			int num=ndk+(i<nmk),ddm=d[i]%m;
			if(!ddm)cnt+=num;
			else sum+=1ll*num*ddm;
		}
		sum/=m;
		write(n-sum-cnt),pc('
');
	}
	return 0;
}