首页 > 其他分享 >题解:CF1608F MEX counting

题解:CF1608F MEX counting

时间:2024-07-27 16:19:36浏览次数:16  
标签:题解 个数 转移 mex 数组 counting MEX rightarrow

题解:CF1608F MEX counting

与其他题解不同,本篇题解是运用辅助数组 $g$ 来解决问题。虽然代码可能要繁琐一点,但是辅助数组的思路适用范围更广一点。


首先还是转化为前 $i$ 个数的 $mex$ 在区间 $[l_i,r_i]$ 内。

我们用 dp 数组 $f_{i,x,c}$ 表示处理到了第 $i$ 个数,当前的 mex 为 $x$,大于 mex 一共有 $c$ 个不同的数。这里我们并不关心大于 mex 的数具体是哪些,而只关心有多少个,因为只要满足大于 mex 一共有 $c$ 个不同的数,方案数都是一样的,我们只需要记录这个一样的方案数即可。注意这里钦定了这 $c$ 个数的顺序,即这 $c$ 个数是有序的(看不懂的话可以根据下面的转移来理解)。

根据定义,考虑有哪些方式能转移到 $f_{i,x,c}$:

  • 这个位置填了一个之前已经出现过的数,这样的数共有 $x+c$ 个,所以转移为 $f_{i-1,x,c}*(x+c)\rightarrow f_{i,j,k}$
  • 这个位置填了大于 mex 且之前没有出现过的数,那肯定是由 $f_{i,x,c-1}$ 转移过来,因为原先有 $c-1$ 个数,而数是有序的,所以新加的数与这 $c-1$ 个数的相对顺序共有 $c$ 种,所以转移为 $f_{i,x,c-1}*c\rightarrow f_{i,j,k}$
  • 第三种情况也是本题的核心,即这个位置填了 mex,这样子我们并不知道有哪些状态能更新到。这时就需要辅助数组 $g$,用 $g_{i,x,c}$ 表示填到了第 $i$ 个数,小于 $x$ 的数都出现过,大于等于 $x$ 共有 $c$ 个不同的数。

这样 $g$ 怎么辅助数组 $f$ 来转移呢?具体流程为,先处理前两个转移,同时更新数组 $g$,然后再用 $g$ 来更新 $f$ 的第三个转移。

  • 对于 $f$ 到 $g$ 的转移,即这个位置填了 mex,显然有 $f_{i,x,c}\rightarrow g_{i,x+1,c}$
  • 对于 $g$ 到 $f$ 的转移,那么对 $g_{i,x,c}$ 分两种情况,即是否出现了 $x$ 这个数。如果出现了,那么应该转移 $g_{i,x,c}\rightarrow g_{i,x+1,c-1}$,如果没有出现,那么应该转移 $g_{i,x,c} \rightarrow f_{i,x,c}$

最后统计答案,对于 $f_{n,x,c}$,由于我们没有关心这 $c$ 个数具体是啥,所以要在剩下的 $n-x$ 个数中选 $c$ 个,因为已经钦定了 $c$ 个数的顺序,所以 $f_{n,x,c}$ 对答案的贡献为 $f_{n,x,c}*\binom{n-x}{c}$

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 2005,mod = 998244353;
int l[N],r[N],n,k;
ll C[N][N],f[2][N][N],g[N][N],ans;
void init()
{
    f[0][0][0] = C[0][0] = 1;
    for(int i = 1;i <= n;i++)for(int j = 0;j <= i;j++)
        C[i][j] = ((j?C[i-1][j-1]:0)+C[i-1][j])%mod;
}
inline int rd()
{
    char c;int f = 1;
    while(!isdigit(c = getchar()))if(c=='-')f = -1;
    int x = c-'0';
    while(isdigit(c = getchar()))x = x*10+(c^48);
    return x*f;
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    n = rd();k = rd();init();
    for(int i = 1;i <= n;i++)
    {int x = rd();l[i] = max(l[i-1],x-k);r[i] = min(x+k,n);}
    for(int i = 1;i <= n;i++)
    {
        for(int x = l[i-1];x <= r[i];x++)for(int c = 0;c <= n;c++)
            g[x][c] = 0;
        for(int x = l[i-1];x <= r[i-1];x++)for(int c = 0;c <= n;c++)
            f[1][x][c] = f[0][x][c],f[0][x][c] = 0;
        for(int x = l[i-1];x <= r[i-1];x++)for(int c = 0;c <= n;c++)//mex=x,cnt(1)=c
        {
            if(l[i] <= x&&x <= r[i])
            {
                (f[0][x][c] += f[1][x][c]*(x+c)) %= mod;
                if(c)(f[0][x][c] += f[1][x][c-1]*c) %= mod;
            }
            (g[x+1][c] += f[1][x][c]) %= mod;
        }
        for(int x = l[i-1];x <= r[i];x++)for(int c = 0;c <= n;c++)
        {
            if(c)(g[x+1][c-1] += g[x][c]) %= mod;
            if(l[i] <= x&&x <= r[i])(f[0][x][c] += g[x][c]);
        }
    }
    for(int x = 0;x <= n;x++)for(int c = 0;c <= n;c++)
        (ans += f[0][x][c]*C[n-x][c]) %= mod;
    cout << ans;
    return 0;
}

这种设辅助数组的思路在许多题中都可以用,值得掌握一下。

标签:题解,个数,转移,mex,数组,counting,MEX,rightarrow
From: https://www.cnblogs.com/max0810/p/18327087/solution-CF1608F

相关文章

  • CF605E Intergalaxy Trips 题解
    Description\(n\)个点的有向完全图。\(i\toj\)的边每天出现的概率均为\(p_{i,j}\),若\(i=j\),有\(p_{i,j}=1\)。每天可以选择一条存在的出边走过去或停留在原地不动。求最优策略下从\(1\)到\(n\)的期望天数。\(n\le10^3\)。Solution设\(f_i\)表示\(i\)......
  • [题解]P2672 [NOIP2015 普及组] 推销员
    P2672[NOIP2015普及组]推销员为了便于操作,将住户信息按疲劳值从大到小排序。那么对于选\(X\)个住户,有\(2\)种情况:选疲劳值前\(X\)大的住户,答案即为\(\sum\limits_{i=1}^Xa[i]+2\times\max\limits_{i=1}^Xs[i]\)。选疲劳值前\(X-1\)大的住户,然后在剩下的住户中,距离比......
  • 《梦醒蝶飞:释放Excel函数与公式的力量》21.2 问题解决策略
     第21章:综合案例分析 21.2问题解决策略在综合案例分析中,解决问题的策略涉及多个步骤,从问题的识别、分析到实施解决方案和评估效果。通过系统的方法和多学科的知识,可以高效地解决复杂的问题。以下将介绍一个具体案例,并通过详细的步骤展示如何制定和实施问题解决策略。案例......
  • Codeforce 962 Div3 C~E 题解
    C题目大意​给定两个字符串a,b,q个询问,每次操作可以将a[i]赋值为任意一个字符,每次询问[l,r]区间内使得sorted(a[l,r])==sorted(b[l,r])的最小操作次数分析​ 不妨先考虑一个区间如何判断sorted后的字串是否相等,发现跟字符出现的次数有关,于是考虑前缀和预处理每一个26......
  • ABC273F Hammer 题解
    ABC273FHammer题解题目大意数轴上有\(n\)个锤子和\(n\)堵墙,第\(i\)个锤子位于\(x_i\),第\(i\)堵墙位于\(y_i\),第\(i\)个锤子可以对应的敲开第\(i\)堵墙。以原点为起点,给定终点\(t\),问最少移动多少个单位长度才能走到\(t\)。必须拿到对应锤子敲开墙才能走过这堵......
  • Codeforces Round 962 (Div. 3) 题解
    A.Legshttps://codeforces.com/contest/1996/problem/A翻译:农夫约翰的农场又迎来了美好的一天。农夫约翰来到农场后,数了数n条腿。众所周知,农场里只住着鸡和牛,一只鸡有2条腿,而一头牛有4条腿。假设约翰农场主数清了所有动物的腿,那么他的农场里最少有多少动物?思路求最少......
  • stata 代码实现熵值法计算 含常见问题解答
    适用:面板数据均可stata版本:无要求例如,使用了一个10年的省级面板数据,含15个指标,现在来计算各地区的熵值法得分。其中,x1x2x3x4x6x7x8x9x11x12x13x14x15是正向指标;而x5x10是负向指标。1.定义面板,定义指标的正负。tssetidyearglobalxlist1"x1x2x3x4x6x......
  • CF585F Digits of Number Pi 题解
    Description给定长度为\(n\)的数字串\(s\)和长度为\(d\)的不含前导零的数字串\(x,y(x\ley)\)。求存在长度至少为\(\left\lfloor\frac{d}{2}\right\rfloor\)的子串是\(s\)的子串的数字串\(t\in[x,y]\)的数量。\(n\le10^3\),\(d\le50\),答案对\(10^9+7\)取......
  • CF578E Walking! 题解
    Description给定一个长度为\(n\)的只包含L,R的字符串\(s\)。构造一个\(n\)排列\(p\)满足\(s[p_i]\nes[p_{i+1}](1\lei<n)\)。最小化\(p\)中\(p_i>p_{i+1}(1\lei<n)\)的数量。\(n\le10^5\),数据保证有解。Solution考虑把\(p\)中的每个极长连......
  • 小信小友逛庙会 题解
    题目id:9774题目描述小信与小友相约逛庙会。但是庙会人很多,他们走散了。庙会能表示成\(n×m\)的矩阵,小信在'\(C\)',小友在'\(D\)','\(.\)'表示能走,'#'表示店铺(也就是不能走)。每分钟,小信可以往\(8\)个方向移动一格,而小友可以移动一次或者两次,每次可以往\(4\)个方向(上下左右)移动一......