首页 > 其他分享 >CF1553I

CF1553I

时间:2023-10-28 10:33:49浏览次数:60  
标签:10 可以 自然数 权值 长度 CF1553I 条链

传送门

description

对于一个 \(1\) 到 \(n\) 的排列 \(p\),第 \(i\) 个位置的权值是 \(p\) 中数字 \(i\),所在的连续自然数段的长度(可以递增,也可以递减)。现在给定一个数组 \(a\),求第 \(i\) 个位置权值为 \(a_i\) 的排列 \(p\) 的个数。

\(n\leq 10^5\)

10.0 s 1024 MiB

solution

数组 \(a\) 中相邻的位置权值相同则可以合成一段长度为权值的链,它们在排列中一定是连续的。例如 \([2,2,2,2,3,3,3,1,1,1]\),我们拆成 \([1,2],[3,4],[5,6,7],[8,8],[9,9],[10,10]\) 几段。显然如果不能恰好拆出这些数链,答案为 0,判掉即可。

现在就是知道有 \(m\) 条数链,每条可以正着也可以反着(长度为 1 的需要特殊处理)。不能有两条链接在一起形成更长的连续自然数段。设 \(g_{i}\) 表示这 \(m\) 条链中钦定有 \(i\) 个链的连接处左右两侧的链可以拼成更长的自然数段,二项式反演得,答案为 \(\sum\limits_{i=0}^m(-1)^i g_{i}\)。下面考虑如何求 \(g_i\)。

设 \(f_{i,j}\) 表示前 \(i\) 条链中钦定 \(j\) 个链的连接处左右两侧的链可以拼成更长的自然数段的方案数,则 \(g_i=f_{m,i}\)。如果不存在长度为 1 的链,转移是好做的:

  • \(f_{0,0}=1\)

  • \(f_{i,j}=2(i-j)\times f_{i-1,j}+f_{i-1,j-1}\)

但是长度为 1 的链会带来较多的麻烦,尝试尝试可以发现这个状态是不好转移的。我们给状态增加一维 01,\(f_{i,j,0/1}\) 表示前 \(i\) 条链中钦定 \(j\) 个链的连接处左右两侧的链可以拼成更长的自然数段,且第 \(i\) 条链是否和前面的链拼接起来的方案数。

这样只要讨论当前链长度是否为 1,以及上一个链长度是否为 1,总共四种情况。可以得出如下代码:(\(n\) 是上文所说的 \(m\),\(b_i\) 表示第 \(i\) 条链的长度,dp 使用了滚动数组)

...
  f[0][0][0]=1;
    for(int i=1; i<=n; i++){
      int x=i&1;
      if(b[i]==1){
        for(int j=0; j<i; j++){
          f[x][j][0]=(f[x^1][j][0]+f[x^1][j][1])*(i-j)%mod;
          if(j){
            if(b[i-1]==1){
              f[x][j][1]=(f[x^1][j-1][0]*2+f[x^1][j-1][1])%mod;
            }
            else{
              f[x][j][1]=(f[x^1][j-1][1]+f[x^1][j-1][0])%mod;
            }
          }
        }
        continue;
      }
      for(int j=0; j<i; j++){
        f[x][j][0]=(f[x^1][j][0]+f[x^1][j][1])*(i-j)*2%mod;
        if(j){
          if(b[i-1]==1){
            f[x][j][1]=f[x^1][j-1][1]+f[x^1][j-1][0]*2;
            f[x][j][1]%=mod;
          }
          else{
            f[x][j][1]=(f[x^1][j-1][1]+f[x^1][j-1][0])%mod;
          }
        }
      }
    }
...

这份代码时间复杂度 \(O(n^2)\),常数特别大,过不去,考虑常数优化。

取模极慢,改成 barret约减,并且对加法不取模,就过了。

code

Submission #230099002 - Codeforces

标签:10,可以,自然数,权值,长度,CF1553I,条链
From: https://www.cnblogs.com/FreshOrange/p/17793757.html

相关文章

  • CF1553I Stairs 题解
    linkSolution虽然但是,这个sb题目真的很sb,不知道怎么评到3400的,也不知道为什么我又没有做出来......