「NOIP2021模拟赛8.23 C」棒棒糖女孩(lollipop)

前言

卧槽,距我上次更新博客已经整整1年了…

关于本人之前一直沉迷whk与fgo,久久未动OI和博客,眼看即将NOIP2021,所以我重新开始写博客记录一下我的康复训练之旅。

题目

题面描述

有一个$1∼n$的排列,其中有$m$个位置上的数缺失了。

已知这个排列的逆序对数恰好为$k$,求有多少种可能的排列。

输入格式

第一行两个正整数$n,k$。

接下来一行$n$个正整数$a_1∼n$,若$a_i=0$则表示这个位置上的数缺失了。

输出格式

共一行,一个整数表示答案。

样例一

input

5 5
4 0 0 2 0

output

2

数据范围与约定

Subtask1(20%):$m≤10$

Subtask2(20%):$n≤100$

Subtask3(30%):0出现的位置为连续一段

Subtask4(30%):无特殊限制

对于100%的数据,$1≤n≤10^5$,$0≤m≤14$,$0≤k≤10^9$

题解

打比赛的时候也就会搓个Subtask2和3,但观察一下m的范围不难发现其实挺sb的,如果meet in middle的话,那复杂度就是$O(C_{14}^{7}*7!)$差不多一千多万的样子,如果写的劣一点可能还带个log。但我们先不说这个,先说做法——首先我们算出除了不确定的数外所有的数的逆序对数,然后我们预处理$cnt[i][j]$表示在第$i$个空位放置第$j$个未出现的数的逆序对数贡献(注意我们未出现的数在数组中为递增的,这点对后面优化计数有帮助)。接下来我们把$m$个空位分成$m/2$,$m-(m/2)$大小的两个部分,并且dfs枚举出这两部分有哪些数(不考虑顺序),在把一个数加入左或者右部分时统计左右部分跨区产生逆序对个数,因为是从小到大放数,所以每次向左边加数时加上右边大小即可。然后考虑区内贡献,首先是考虑放入数的顺序对于非空位贡献,这部分通过$cnt$数组可轻松计算,然后考虑区内贡献,因为我们从小到大加入点,我们考虑开个$res$计算在$i$这个数放入前$1 ∼ i$内有多少数未被放入,那么这$res$个数必然放入i后,产生$res$的贡献,由此我们可以把树状数组的$log$统计变为$O(1)$统计,至于答案对于左边开个桶记录,右边加对应符合条件的桶的贡献就可以了。

代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define Maxn 100005
#define Maxm 20
#define gc getchar
#define W while
#define isd isdigit
#define LL long long
#define lowbit(x) (x&(-x))
#define F(i,x,y) for (LL i=x;i<=y;i++)
#define D(i,x,y) for (LL i=x;i>=y;i--)
using namespace std;
struct FastIO{
	static const LL S=1048576;
	char buf[S],*L,*R;LL stk[20],Top;
	~FastIO(){clear();}
	inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}
	inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
	inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}
	inline void endl(){pc('\n');}
	FastIO& operator >> (LL& ret){ret=0;LL f=1;char ch=nc();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}ret*=f;return *this;}
	FastIO& operator >> (char* s){register LL Len=0;register char ch=nc();while(ch!='\n'){*(s+Len)=ch;Len++;ch=nc();}}
	FastIO& operator << (LL x){if(x<0){pc('-');x=-x;}do{stk[++stk[0]]=x%10;x/=10;}while(x);while(stk[0]) pc('0'+stk[stk[0]--]);return *this;}
	FastIO& operator << (char ch){pc(ch);return *this;}
	FastIO& operator << (string str){register LL Len=str.size()-1;for(stk[0]=0;Len>=0;Len--) stk[++stk[0]]=str[Len];while(stk[0]) pc(stk[stk[0]--]);return *this;}
}fin,fout;
LL k,n,a[Maxn],T[Maxn],top=0,tot=0,tree[Maxn],cnt[Maxm][Maxm],K=0,L[Maxm],R[Maxm],C[Maxn*14],P[Maxn*14],TOT=0;bool vis[Maxn],flagL[Maxm],flagR[Maxm];
LL ans=0;
inline void add(LL i,LL x){W(i<=n)tree[i]+=x,i+=lowbit(i);}
inline LL ask(LL i){LL res=0;W(i)res+=tree[i],i-=lowbit(i);return res;}
inline void dfsL(LL now,LL sum,LL limit)
{
	if (now>limit){C[sum]++;P[++TOT]=sum;return;}LL res=0;
	F(i,1,limit)
	{
		if (flagL[i]) continue;
		flagL[i]=1;
		dfsL(now+1,sum+cnt[now][L[i]]+res,limit);
		flagL[i]=0;res++;
	}
}
inline void dfsR(LL now,LL sum,LL O,LL limit,LL limit2)
{
	if (now>limit){if (O>=sum) ans+=C[O-sum];return;}LL res=0;
	F(i,1,limit)
	{
		if (flagR[i]) continue;
		flagR[i]=1;
		dfsR(now+1,sum+cnt[limit2+now][R[i]]+res,O,limit,limit2);
		flagR[i]=0;res++;
	}
}
inline void dfs(LL now,LL topL,LL topR,LL T)
{
//	cout<<now<<" "<<topL<<" "<<topR<<" "<<T<<" "<<top/2<<" "<<top-(top/2)<<endl;
	if (now>top) 
	{
		F(i,1,TOT) C[P[i]]=0;
		TOT=0;
		topL--,topR--;
//		F(i,1,topL) cout<<L[i]<<" ";
//		cout<<endl;
//		F(i,1,topR) cout<<R[i]<<" ";
//		cout<<endl;
//		cout<<"T="<<T<<endl;
		if (T>k) return;
		dfsL(1,0,topL);
		dfsR(1,0,k-T,topR,topL);return;
	}
	if (topL<=top/2) L[topL]=now,dfs(now+1,topL+1,topR,T+topR-1),L[topL]=0;
	if (topR<=top-(top/2)) R[topR]=now,dfs(now+1,topL,topR+1,T),R[topR]=0;
}
int main()
{
//	freopen("s.in","r",stdin);
//	freopen("s.out","w",stdout);
	fin>>n>>k;
	F(i,1,n) fin>>a[i],vis[a[i]]=1;F(i,1,n) if (!vis[i]) T[++top]=i;
	F(i,1,n) if (a[i]) add(a[i],1),tot+=ask(n)-ask(a[i]);else{K++;F(j,1,top) cnt[K][j]=ask(n)-ask(T[j]);}
	F(i,1,n) if (a[i]) add(a[i],-1);D(i,n,1) if (a[i]) add(a[i],1);else{F(j,1,top) cnt[K][j]+=ask(T[j]-1);K--;}D(i,n,1) if (a[i]) add(a[i],-1);
	k-=tot;if (k>Maxn*14){return puts("0"),0;}if (k>=0) dfs(1,1,1,0);fout<<ans<<'\n';return 0;
}
/*
9 4
1 2 3 0 4 5 6 0 0

5 5
4 0 0 2 0
*/
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇