最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

Codeforces 1671 F Permutation Counting 题解

来源：博客园


(资料图片仅供参考)

题目链接

把\(p_i>p_{i+1}\)的位置个数称为间隔数

首先想到一个暴力做法。从小到大挨个添加1-n中的每个数，注意到添加数i时，只能添加到当前序列的最后11个位置中，否则逆序对数就会超。令\(dp_{i,j,p,msk}\)表示当前添加到数i，当前逆序对数为j，间隔数为p，msk是一个集合表示当前序列最后11个位置中哪些满足\(p_i>p_{i+1}\)。转移比较简单。但是这个dp的第一维是n，但n很大。矩阵快速幂也是不行的，后面的维度也很大。

我们考虑把一个长度为n的排列分段。令\(mx_i\)表示\(max_{j=1}^i p_j\)。我们找到从左往右第一个满足\(mx_i=i\)的位置，也就是第一个满足\(p_1\cdots p_i\)是一个排列的位置，然后把1-i分为一段，数组剩下的部分统一减i，然后不断进行同样的分段操作直到序列用完。发现分出的每一段都是一个"小的排列"，且左侧的一个小排列中的所有\(p_i\)都小于右侧任意一个小排列中的\(p_i\)。注意到两个段之间不会贡献任何的逆序对数或间隔数，所以排列p的逆序对数和间隔数等于每一小段内部的逆序对数和间隔数之和。

一个小段的长度如果>12，那它的逆序对数就>11，所以此时的p肯定不合法。证明：令小段为一个1-k的排列\(b_1\cdots b_k\)，其前缀max为\(c_1\cdots c_k\)。对于任意\(1\le ib_i\)且加入j时有不止一个这样的x，我们现在加入i只是消耗了加入j时产生的一个逆序对而已。综上，总的逆序对个数一定会\(\ge k-1\)。因此我们可以用一个简单的背包算出数组\(f_{i,j,p}\)表示长度为i，逆序对数为j，间隔数为p的小段个数。为了保证对于任意\(1\le i

算出f数组之后为了得到n的答案，可能会想到多项式快速幂什么的，其实根本不需要多项式技巧。注意到小段的长度\(>1\)时，逆序对数和间隔数都不为0；而小段长度为1时这两个值都为0。所以长度>1的小段个数\(\le 11\)，再做一次背包，然后用插板法把其他长度为1的小段插进去即可。

没仔细算时间复杂度，反正不高。

点击查看代码
#include #define rep(i,n) for(int i=0;i#define pdd pair #define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){  #ifdef LGS  freopen("in.txt","r",stdin);  freopen("out.txt","w",stdout);  #endif}void termin(){  #ifdef LGS  std::cout<<"\n\nEXECUTION TERMINATED";  #endif  exit(0);}using namespace std;const LL MOD=998244353;LL qpow(LL x,LL a){LL res=x,ret=1;while(a>0){if(a&1) (ret*=res)%=MOD;a>>=1;(res*=res)%=MOD;}return ret;}LL t,n,k,x,dp[4100][20][20][20];//dp[msk][k][x][lst]LL dp2[20][30][20][20];//dp2[cnt][lensum][k][x]LL rinv[100];LL C(LL nn,LL mm){  LL ret=1;for(LL i=nn;i>=nn-mm+1;--i) (ret*=i)%=MOD;  repn(i,mm) (ret*=rinv[i])%=MOD;  return ret;}int main(){  fileio();  rep(i,95) rinv[i]=qpow(i,MOD-2);  LL lim=12;  dp[0][0][0][0]=1;  rep(msk,1<0) continue;    LL val=dp[msk][kk][xx][lst],addk=0;    for(int nxt=lim-1;nxt>=0;--nxt)    {      if(msk&(1<nxt)][nxt]+=val)%=MOD;    }  }  rep(i,1<>t;  rep(tn,t)  {    cin>>n>>k>>x;    LL ans=0;    rep(cnt,k+1) for(int sz=cnt+cnt;sz<=24;++sz)    {      LL val=dp2[cnt][sz][k][x];      if(val==0||sz>n) continue;      LL tot=n-sz,spas=cnt+1;      LL mul=C(tot+spas-1,spas-1);      (ans+=val*mul)%=MOD;    }    cout<

关键词： 形成一个 时间复杂度