洛谷 P4933 大师

题面

 

(实名推荐：本题的出题人小哥哥打球暴帅哦！(APIO/CTSC/WC的时候一起打过球w，而且大学在我隔壁喔) )

没仔细看数据范围的时候真是摸不着头脑。。。还以为要 O(N^2) dp 爆锤。。

后来发现v<=20000，这能干啥呢？

至少我的暴力是可以趁机跑过了2333，暴力如下：

    我们枚举每一种公差，然后每一轮     先把所有 a[j]-a[i]=公差 的 i在图中连一条到j的边(i<j)， 再跑一遍拓扑排序求这种公差的方案数。(因为任意一种选法都可以且仅可以对应到唯一的一轮的建出的DAG(为什么是DAG这个不用证吧。。。)上的一条链，我们直接统计总链数即可)

 

    这里有一点疏忽，因为仅仅一个数构成等差数列这种情况会在每一轮都被算一遍，而我们最后只需要算它一次。一种解决办法是把每轮的答案-n，然后所有算完了之后再+n。

 

算一下这个暴力的复杂度，O(2*N^2*log(N) + N*V )，后面拓扑排序总边数的 O(N^2)被前面更大的那个复杂度给按下去了，而那个复杂度是因为我懒得写基数排序而多出来的，但因为本题 2*N^2*log(N) 与 N*V 在 N与V同时取到最大值的时候恰好相等，所以我就懒得优化这个玩意了hhhh

 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define pb push_back
const int N=1005,ha=998244353;

inline int add(int x,int y){ x+=y; return x>=ha?x-ha:x;}
inline void ADD(int &x,int y){ x+=y; if(x>=ha) x-=ha;}

vector<int> g[N];
int f[N],n,h[N],num,ans,id[N];
struct node{
	int x,y,z;
	bool operator <(const node &u)const{
		return z<u.z;
	}
}a[N*600+5];

inline void TSort(){
	queue<int> q;
	for(int i=1;i<=n;i++) if(!id[i]) q.push(i);
	
	for(int x;!q.empty();q.pop()){
		x=q.front(),ADD(ans,f[x]);
		for(int i:g[x]){
			ADD(f[i],f[x]);
			if(!(--id[i])) q.push(i);
		}
	}
}


inline void solve(){
	for(int i=1;i<n;i++)
	    for(int j=i+1;j<=n;j++) a[++num]=(node){i,j,h[j]-h[i]};
	sort(a+1,a+num+1);
	
	for(int i=1,j;i<=num;i=j){
		fill(f+1,f+n+1,1),j=i,memset(id,0,sizeof(id));
		for(int i=1;i<=n;i++) g[i].clear();
		
		while(j<=num&&a[j].z==a[i].z) g[a[j].x].pb(a[j].y),id[a[j].y]++,j++;
		
		TSort(),ADD(ans,ha-n);
	}
	
	ADD(ans,n);
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",h+i);
	solve(),printf("%d\n",ans);
	return 0;
}