526互联

Educational Codeforces Round 149 (Rated for Div. 2)

发布时间 2023-10-21 09:44:47作者: gan_coder

这场D被切穿了。

A题
答案为
x 或者 x-1 1

B题
答案就是最长的连续一段的长度+1

证明的话大概可以将它看成是几段连续上升和下降的段，然后在峰谷、峰顶分别填上最小、最大，剩下的就依次递增或递减就行。

C题
将一段连续的0/1视作一个块，那么我们最小化这个块的数量就行。

D题如果猜到如果有解那么ans<=2，就变得非常简单。

E题

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#define A puts("YES")
#define B puts("NO")
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
using namespace std;
typedef double db;
typedef long long ll;
const int N=1e6+5;
const ll mo=998244353;
ll n,a[N],k,c[N],b[N],d[N];
vector<ll> v;
ll f[N],ans,size,tot,res;
int main()
{
//	freopen("data.in","r",stdin);	
	
	
	scanf("%lld",&k);
	n=1<<k;
	
	fo(i,1,n){
		a[i]=-1;
	}
	
	fo(i,1,n) {
		scanf("%lld",&d[i]);
		a[d[i]]=i;
	}
	
	f[0]=1; 
	b[0]=1;
	fo(i,1,n) {
		f[i]=f[i-1]*i%mo;
		b[i]=b[i-1]*2ll%mo;
	}
	
	if (a[1]!=-1) v.emplace_back(a[1]),res++;
	
	ans=1;
	fo(j,0,k-1) {
		fo(i,b[j]+1,b[j+1]) {
			if (a[i]!=-1) {
				v.emplace_back(a[i]);
				tot++;	
			}
		}
		
		size=n/b[j+1];
		fo(i,1,b[j+1]) c[i]=0;
		
		for (auto i:v) {
			if (i%size==0) c[i/size]++;
			else c[i/size+1]++;
		}
		
		fo(i,1,b[j+1]) if (c[i]>1) ans=0;
		
		ll z=0;
		fo(i,1,b[j+1]) {
			if (i&1) {
				if (c[i] && c[i+1]) z++;
			}
		}
		
		ans=ans*f[b[j]-tot]%mo*b[ b[j]-(tot+res-z)]%mo;
		res+=tot;
		tot=0;
	}
	
	fo(i,1,n) {
		if (i&1) {
			if (d[i]>n/2 && d[i+1]>n/2) ans=0;
		}
	}
	
	printf("%lld",ans);
    return 0;
}