首页 > 其他分享 >[ARC138E] Decreasing Subsequence

[ARC138E] Decreasing Subsequence

时间:2025-01-08 09:05:21浏览次数:6  
标签:int Max rep Subsequence fac Decreasing 序列 mul ARC138E

[ARC138E] Decreasing Subsequence

题意

给出 \(3\leq n \leq 5000,2\leq k \leq (n+1)/2\),对所有长度为 \(n\) 的满足 \(0\leq a_i \leq i\) 且正数项两两不同的序列 \(a\),求长度为 \(k\) 的元素非 \(0\) 的下降子序列个数之和。

思路

先刻画序列。

对所有 \(a_i\) 减去 \(1\),新的序列是 \(a'\)。

对于所有 \(a_i'\neq -1\),必须有 \(a_i'<i\)。连接一条 \(i \to a_i'\) 的边,满足这条边必须方向向前。而且由于所有非负整数互不相同,建出来的图必须是若干条不相交的链。

比如下面酱子,就是一个合法的 \(a'\) 了。


接下来刻画下降子序列

下降子序列 \(\{s_i\}\),必须满足这些点有出边,而且它们的出边刚好形成一个像彩虹一样的包含形状。

比如上图中标黄色和标黑色分别就是其中两组合法子序列。


合法的连边方案和合法的序列是双射。我们要对每个合法的连边方案计算有多少长度为 \(k\) 的合法子序列。

子序列的刻画太难拍成状态了,不好算。于是我们转为算每种合法的大小为 \(k\) 的“彩虹”连边有多少合法的连边方式吧。这好啊,还不用考虑算重,因为每种不同的子序列出现在同一个序列里面,你也得分别算贡献的。

对于一组彩虹边,起点有 \(k\) 个,分别是 \(s_1 \sim s_k\),终点也有 \(k\) 个,分别是 \(t_1 \sim t_k\)。计算序列个数。每个 \(s_i\) 可以向后连长度任意的链,每个 \(t_i\) 可以向前连长度任意的链。剩下没有被用到的点,可以随便分成任意条链。

枚举 \(l\) 表示终点和终点连的链的点的个数,\(r\) 表示起点和起点连的链的点的个数。\(n \brace m\) 是第二类斯特林数的意思。

答案是:(\(n+1\) 是因为图里面还有 \(0\) 号点)

\[\sum_{l=k} \sum_{r=k}^{l+r\le n+1} \binom{n+1}{l+r} {l \brace k} {r \brace k} f_{n+1-l-r}\\ f_i = \sum_{x=1}^i {i \brace x} \]

解释一下组合意义:上面那条就是在 \(n+1\) 个点里面,选出 \(l+r\) 个点,并且左边分 \(l\) 个,右边分 \(r\) 个,左右都分别分成 \(k\) 条链,每条链上点的顺序和链于链之间的顺序都是按照编号有序的。\(f_i\) 就表示剩下 \(i\) 个点分成任意组链的方案数。

预处理第二类斯特林数,预处理 \(f_i\)。时间复杂度 \(O(n^2)\)。

code

代码好写啊。

#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
namespace hesitate {
	constexpr int N=5e3+7,Max=5e3+1,mod=1e9+7;
	int add(int a,int b) { return a+b>=mod ? a+b-mod : a+b; }
	void _add(int &a,int b) { a=add(a,b); }
	int mul(int a,int b) { return 1ll*a*b%mod; }
	void _mul(int &a,int b) { a=mul(a,b); }
	int ksm(int a,int b=mod-2) {
		int s=1;
		while(b) {
			if(b&1) _mul(s,a);
			_mul(a,a);
			b>>=1;
		}
		return s;
	}
	int s[N][N],f[N],fac[N],ifac[N];
	int n,k;
	void init() {
		s[0][0]=1;
		rep(i,1,Max) rep(j,1,i) s[i][j]=add(s[i-1][j-1],mul(j,s[i-1][j]));
		f[0]=1;
		rep(i,1,Max) rep(j,1,i) _add(f[i],s[i][j]);
		fac[0]=1;
		rep(i,1,Max) fac[i]=mul(fac[i-1],i);
		ifac[Max]=ksm(fac[Max]);
		per(i,Max-1,0) ifac[i]=mul(ifac[i+1],i+1);
	}
	int C(int n,int m) { return mul(fac[n],mul(ifac[m],ifac[n-m])); }
	int ans;
	void main() {
		sf("%d%d",&n,&k);
		init();
		rep(l,k,n+1-k) rep(r,k,n+1-l) {
			_add(ans,mul(C(n+1,l+r),mul(mul(s[l][k],s[r][k]),f[n+1-l-r])));
		}
		pf("%d\n",ans);
	}
}
int main() {
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("my.out","w",stdout);
    #endif
	hesitate :: main();
}

标签:int,Max,rep,Subsequence,fac,Decreasing,序列,mul,ARC138E
From: https://www.cnblogs.com/liyixin0514/p/18658452

相关文章

  • CF1621G Weighted Increasing Subsequences 题解
    题目链接点击打开链接题目解法这种题就感觉每一步都不难想,但串在一起就不会显然考虑位置\(x\)作为\(lis\)的一部分,合法的\(lis\)的个数合法的约束是:令\(lis\)的最后一个位置为\(last\),满足\(\max\{a_{last+1},...,a_n\}>a_x\)不难发现,合法的\(last\)是一段区间......
  • 浙大数据结构:01-复杂度2 Maximum Subsequence Sum
    数据结构MOOCPTA习题01-复杂度2MaximumSubsequenceSum#include<iostream>usingnamespacestd;constintM=100005;inta[M];intmain(){ intk; cin>>k; intf=1; for(inti=0;i<k;i++) { cin>>a[i]; if(a[i]>=0)//如......
  • CF 2001 D. Longest Max Min Subsequence(*1900) 思维
    CF2001D.LongestMaxMinSubsequence(*1900)思维题目链接题意:给你一个长度为\(n\)的序列\(a\),设\(S\)是\(a\)的所有可能的非空子序列的集合,且没有重复的元素。你的目标是找出\(S\)中最长的序列。如果有多个序列,请找出将奇数位置上的项乘以\(−1\)后,使词序最小......
  • Strings, Subsequences, Reversed Subsequences, Prefixes
    题目大意给定两个字符串s和t,求出在s里面有多少个本质不同的子序列,使得该序列的前缀包含t,且该序列的反串也包含t即s的子序列=t+x+反t‘首先要确定是否有,就是判断我的S字符串中有没有包含T字符串for(l=0;l<n;l++){ if(s[l]==t[num])num++; if(num==m)bre......
  • CF568E Longest Increasing Subsequence 题解
    Description给定一个长度为\(n\)的有\(k\)个空缺的序列。你有\(m\)个数可以用于填补空缺。要求最大化最长上升子序列的长度。\(n,m\le10^5\),\(k\le10^3\)。Solution容易发现只需要先构造出LIS上的位置的值,对于其余未填位置随便填,所以构造LIS时就不需要考虑出......
  • P3131 [USACO16JAN] Subsequences Summing to Sevens S
    传送锚点:[USACO16JAN]SubsequencesSummingtoSevensS-洛谷题目描述FarmerJohn's\(N\)cowsarestandinginarow,astheyhaveatendencytodofromtimetotime.EachcowislabeledwithadistinctintegerIDnumbersoFJcantellthemapart.FJwould......
  • 题解:AT_abc352_d [ABC352D] Permutation Subsequence
    虽然比赛没打,但是想来水估值发表思路。题意给你一个\(1\simn\)的排列,让你从中找一段长为\(k\)的子序列,使得这个子序列中的元素排序后数值连续。分析题意转换一下,先用结构体存储每个元素的编号和数值,按照数值排序。于是这道题就成了:一个序列,让你求所有长\(k\)的子段中......
  • LeetCode 2263. Make Array Non-decreasing or Non-increasing
    原题链接在这里:https://leetcode.com/problems/make-array-non-decreasing-or-non-increasing/description/题目:Youaregivena 0-indexed integerarray nums.Inoneoperation,youcan:Chooseanindex i intherange 0<=i<nums.lengthSet nums[i] to num......
  • [ABC362E]Count Arithmetic Subsequences
    题目大意给定\(N\)个数字的序列,每个元素为\(a[i]\),问长度为i的数字序列是由多少个子序列构成的?定义数字序列:如果\(a[i]-a[j]==a[k]-a[i]\),则\(a[j],a[i],a[k]\)构成数字序列数据范围\(N\leq80,a_i\leq10^9\)题解一看到这个数据范围,就和\(a[i]\)没关系,肯定是和\(N\)有......
  • 题解:CodeForces 843A Sorting by Subsequences[模拟/排序]
    CodeForces843AA.SortingbySubsequencestimelimitpertest:1secondmemorylimitpertest:256megabytesinputstandardinputoutputstandardoutputYouaregivenasequence\(a_1, a_2, ..., a_n\)consistingofdifferentintegers.Itisrequiredtos......