【HDU3706】Second My Problem First(单调队列)

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 05 月 18 日

Give you three integers n, A and B.
Then we define Si = Ai mod B and Ti = Min{ Sk | i-A <= k <= i, k >= 1}
Your task is to calculate the product of Ti (1 <= i <= n) mod B. 题意:略了吧。。。结果是求Ti模B的乘积。
单调队列,区间是k(i-A<=k<=i),如果单调队列不太了解请点这里

#include <cstdio>
#include <algorithm>
using namespace std;
#define maxlen 10005
int ind[maxlen],val[maxlen];
int main(){
	//freopen("1.txt","r",stdin);
	int n,A,B;
	long long res,S;
	while(scanf("%d%d%d",&n,&A,&B)!=EOF)
	{
                int *end=val,*beg=val;
		S=1,res=1;
		for (int i=1;i<=n;i++)
		{
			end=lower_bound(beg,end,S=S*A%B);
			*end=S;
			ind[end-val]=i;
			++end;
			while(ind[beg-val]<i-A) ++beg;
			res =(res*(*beg))%B;
		}
		printf("%d\n",res);
	}
}

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期五, 2017 年 12 月 15 日