自动搬运

查看原文

来自洛谷，原作者为

	Misaka19280 **

搬运于2025-08-24 22:04:23，当前版本为作者最后更新于2018-08-28 22:55:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题是洛谷八月月赛T1,按照出题人的说法这题是普及-的难度~~（那我怕不是完了），于是我评价了一个蓝题~~

我们先口胡人工模拟一波

我们来列一个表（直接复制@阿姆斯特朗炮 巨佬的题解中的表，但是他的那篇题解也感谢我了所以我就搬了过来 放一个他的友链）

↑授权图

						a1 a2 a3

                   a1+a2  a2+a3  a3+a1

			a1+2a2+a3 	a2+2a3+a1	a3+2a1+a2

		a1+3a2+3a3+a1 a2+3a1+3a3+a2 a3+3a1+3a2+a3

我们抽样调查（滑稽）一下第一列

						a1

					   a1+a2

					 a1+2a2+a3

				   a1+3a2+3a3+a1

咳咳

看出来什么了吗

没看出来？

好吧，我们把系数抽出来

1 1 1 1 2 1 1 3 3 1

这个裸的杨辉三角看出来了吧= =

于是就非常开心了

求出杨辉三角

对于每次询问，直接求出从x开始的后面每一位乘以对应的杨辉三角形第x层的系数就可以了

复杂度O(qy)可以接受

当然要预处理出来杨辉三角形

下面我们上代码

Const 
	maxx=2001;
	moha=998244353; //不要在意这个变量的名称

Var
	a:array[1..1000000]of longint;
	yh:array[1..maxx,1..maxx]of longint;
	n,i,m,x,y,j,cnt,xx:longint;
	ans:qword;
	
Begin
	readln(n);
	for i:=1 to n do
		read(a[i]);
	for i:=1 to maxx do
		begin
			yh[i,1]:=1;
			yh[i,i]:=1;
			for j:=2 to i-1 do
				yh[i,j]:=(yh[i-1,j-1]+yh[i-1,j]) mod moha; //杨辉三角形要直接取膜，不然会爆
		end; //预处理杨辉三角形
	readln(m);
	for i:=1 to m do
		begin
			read(x,y);
			ans:=0;
			j:=y;
			cnt:=1; //这个cnt完全没必要，但是总觉得写了更清楚
			inc(x); //这里inc(x)需要自己想一下原因,emm算了告诉你吧，你比如说x=1，就是求第y和y+1的值，你要是不inc的话就只求y了
			xx:=x;
			while x>0 do
				begin
					ans:=(ans+a[j]*yh[xx,cnt]) mod moha;
					j:=j mod n+1;
					dec(x);
					inc(cnt);
				end;
			writeln(ans);
		end;
End.

什么你跟我说Pascal看不懂？= =

那就光看思路，去其他的楼看代码= =（虽然我的思路并不怎么清晰Orz）

还有一个洛谷的题目数量统计bug，跟这题有关

一个奇怪的现象

其实月赛的时候我为了测试大一点的数据手残打了个文件然后就获得了0分的好成绩