比赛地址：https://www.luogu.com.cn/contest/26777

这个题，还真是需要 $⌈$ 创新思维 $⌋$ 。

zzd 大佬（他 AK 虐全场）

A. 横跨新泰

~~突然暴露坐标~~

题意简述

我们定义一个路径为从一个十字路口到另一个十字路口经过的边（无向），路径的距离为走过的边的数目。
当某两条路径的起点、终点十字路口均相同时，两个路径相同。
路径的中点是当距离到达总路径距离的一半时所经过的十字路口。
问题是：给定 $n$ ， $m$ 表示横向道路数，纵向道路数（上图 $n=3$ ， $m=4$ ），请问有多少对不同的十字路口，满足它们之间存在一条路径的中点是两点之间连线的中点（如上图）？
由于答案可能很大，所以对 $998244353$ 取模输出。
数据范围： $n<5000$ ， $m<2000$ 。

思路

由于~~出题人的数据很毒瘤，要必须写出满分解~~，下面介绍 $O(1)$ 解法。

考虑两个点 $(a,b)$ ， $(c,d)$ 满足题意的条件。易得：

$a$ 与 $c$ ， $b$ 与 $d$ 同为奇数或偶数，且 $a\not=c$ ， $b\not=d$ 。

则有四种情况：

同为偶偶，偶奇，奇偶，奇奇。

同一种情况中的两个点，可以任意组合，形成合法解。

那么，第一步就是算出每种情况中的点的个数。

qq=((n+1)/2)*((m+1)/2);
qo=floor(n/2)*((m+1)/2);
oq=((n+1)/2)*floor(m/2);
oo=floor(n/2)*floor(m/2);

//q是奇，o是偶
//公式自己可推

第二步：任意组合。

ans=(//同种两个点任意组合 
    qq*(qq-1)+
    qo*(qo-1)+
    oo*(oo-1)+
    oq*(oq-1)
    )/2;//方案重复了，/2

然后输出！

CODE

#include<bits/stdc++.h>
using namespace std;
unsigned long long n,m,qq,oo,qo,oq,ans;
int main()
{
	cin>>n>>m;
	qq=((n+1)/2)*((m+1)/2);
	qo=floor(n/2)*((m+1)/2);
	oq=((n+1)/2)*floor(m/2);
	oo=floor(n/2)*floor(m/2);
	ans=qq*(qq-1)+qo*(qo-1)+oo*(oo-1)+oq*(oq-1);
	cout<<(ans/2)%998244353;
	return 0;
}

B. 反反正正

题意简述

给定 $k$ 条序列。
每条序列被分成了 $n$ 块，每一块都有一个颜色黑/白，0 为黑色，1 为白色。
操作：选定一个块，让这个块左侧及其自身所有块反色。
当操作 $p$ 次后所有块为黑色时，若 $p$ 为奇数，则 $ans\gets ans+a_i$ 。
数据范围： $k<5$ ， $a<2000$ ， $m<1000$ 。

思路

此题与洛谷P2708 硬币翻转类似。

我们可以发现假如当前块状态和之前所有块的状态不一样的时候，我们就要进行操作。因为如果不修改那么之后不管怎样改变状态都不能让所有块的状态都一样了。

这样最后我们这样做块肯定都是一样的了。

然后判断所有块是否都为黑，如果都不为黑那么就还要再操作一次。

那么，做法如下：

从第一个块开始,两两比较
如果不一样就翻转（ $p\gets p+1$ ）。
全部翻转后，如果最后一个块为白，翻转次数还要 $+1$ 。

因为我们不需要真的进行操作，所以只需记录 $p$ 即可。

CODE

#include<bits/stdc++.h>
using namespace std;
int n,a[1000+5],m,ans=0,v[1000+5];
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int cnt=0;
		scanf("%d%d",&m,&n);
		for(int i=1;i<=n;i++)
			scanf("%d",a+i);
		for(int i=1;i<=n-1;i++)
			if(a[i]!=a[i+1])
				cnt++;
		if(a[n]==1)
			cnt++;
		if(cnt%2==1)
			ans+=m;
	}
	printf("%d",ans);
	return 0;
}

C. 正正反反

题意简述

洛谷题面不准。

与B题一样，只是变成了二维。数据范围也更毒瘤了。
操作变为了：选定一个块，让这个块左上所有块反色。
给定 $k$ 个矩阵，对于每个矩阵：第一行六个正整数 $a$ 、 $m$ 、 $A$ 、 $B$ 、 $C$ 、 $D$ ，表示矩阵被分为了 $m\times m$ 块方块， $ABCD$ 是随机函数参数。
数据范围： $k<100$ ， $a<2000$ ， $m<10^{10}$ （你没看错）， $A,B,C,D<10$ 。

随机函数是：

memset(color,0,sizeof(color));
for(int i=1;i<=m;++i)
for(int j=1;j<=m;++j)
color[i][j]=(A^B|C+(D*color[i-1][j]|color[i][j-1]))&1;

思路

根据数据范围，我们需要 $O(1)$ 算法。

在推理后，发现能否抢到红包，只与 $(1,1)$ 处的块的颜色有关。

CODE

#include<bits/stdc++.h>
using namespace std;
int ans=0,n;
int rander(int A,int B,int C,int D)
{
	int color[3][3];
	memset(color,0,sizeof(color));
	color[1][1]=(A^B|C+(D*color[1-1][1]|color[1][1-1]))&1;
	return color[1][1];
}
int main()
{ 
	int a,b,c,d,m;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d%d%d%d",&m,&a,&a,&b,&c,&d);
		ans+=m*rander(a,b,c,d);
	}
	printf("%d",ans);
	return 0;
}

D. 审视自我

题意简述

给定一段评测记录 $S$ ，且 $S$ 中的每个元素 $status_i\in{A,W,R,T,U,M}$ ，分别表示 AC，WA，RE，TLE，UKE，MLE。
在此评测记录中，随机看一段连续记录，看其中的 AC 占比（介于 0，1 之间）作为分数。
求分数期望 $\times 10000$ 的整数部分。
数据范围： $n<1000000$ 。

思路

循序渐进

$O(n^3)$ 算法

暴力枚举 $1$ 到 $n$ 表示 $\lceil$ 一段连续记录 $\rfloor$ 的长度。

$\quad$ 暴力枚举 $1$ 到 $n$ 减长度加 $1$ 表示 $\lceil$ 一段连续记录 $\rfloor$ 的起始点。

$\quad$ $\quad$ 设定计数器为 0。

$\quad \quad$ 暴力枚举 0 到长度减一表示 $\lceil$ 一段连续记录 $\rfloor$ 的每个元素 now。

$\quad\quad\quad$ 如果 $status_{start+now-1}$ 为 A，则计数器加一。

$\quad \quad$ 枚举完了。

$\quad\quad$ 分数变为原分数加计时器除以长度的值。

$\quad$ 枚举完了。

枚举完了。

最后输出分数乘以 $10000$ 再除以从 1 加到 $n$ 的值即可。

CODE

for(int i=1;i<=n;i++)
{
    num+=i;
    for(int j=1;j<=n-i+1;j++)
	{
		int tal=0;
		num++;
		for(int k=0;k<=i-1;k++)
			if(a[j+k-1]=='A')
				tal++;
		ans+=tal*1.0/i;
	}
}
cout<<round(ans/num*10000);

$O(n^2)$ 算法

使用前缀和记录：

for(int i=1;i<=n;i++)
	p[i]=(p[i-1]+(a[i-1]=='A'));

那么就可以把暴力枚举 0 到长度减一表示 $\lceil$ 一段连续记录 $\rfloor$ 的每个元素 now 这个循环去掉了。

for(int i=1;i<=n;i++)
	for(int j=1;j<=n-i+1;j++)
		ans+=(p[j+i-2]-p[j-2])*1.0/i,num++;
cout<<round(ans/num*10000);

$O(n)$ 算法（正解）

设 n=5。

尝试把 j 这一层循环展开，得到：

i=1 p1-p0 + p2-p1 + p3-p2 + p4-p3 + p5-p4 
    = p5-p0
i=2 p2-p0 + p3-p1 + p4-p2 + p5-p3 
    = p5-p0 + p4-p1
i=3 p3-p0 + p4-p1 + p5-p2 
    = p5-p0 + p4-p1 + p3-p2
i=3 p4-p0 + p5-p1 
    = p5-p0 + p4-p1
i=4 p5-p0

发现规律了吗？

CODE

	if(n%2==1)
	{
		int mid=(n+1)/2;
		for(int i=1;i<=mid;i++)
		{
			tal+=p[n-i+1]-p[i-1];
			if(i<mid)
				ans+=tal*1.0/i + tal*1.0/(n-i+1);
			else
				ans+=tal*1.0/i;
		}
	}	
	else
	{
		int mid=n/2;
		for(int i=1;i<=mid;i++)
		{
			tal+=p[n-i+1]-p[i-1];
			ans+=tal*1.0/i + tal*1.0/(n-i+1);
		}
	}
	cout<<round(ans/num*10000);

E. 合并欢喜

题意简述

给定 $T$ 圈数。
规定一个操作：设一个数 $x$ 的旁边的一个数为 $a$ ，使 $x$ 变为它原来的 $a$ 倍，并移除 $a$ 这个数，剩下的数重新结为一个圈。
进行若干次操作后，只会剩下一个数。
输出对于每个圈，进行若干次操作后，这个最后一个数的最大值。
数据范围： $T<5$ ， $n<1000$ ， $0<a<100$ 。

思路

经过证明，答案其实就是这一圈数所有数的乘积。有理数乘法满足交换律、结合律。~~这个题的证明需要群论的知识~~。

CODE

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
unsigned long long n,ans,a;
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		cin>>n;
		ans=1;
		for(unsigned long long i=1;i<=n;i++) 
			cin>>a,ans=((a*ans)%mod);
		printf("%llu\n",ans);
	}
	return 0;
}