Atcoder abc267

發表於 更新於 分類於 ， Disqus： 文章字數： 628 所需閱讀時間 ≈ 2 分鐘
G(排列组合)

https://atcoder.jp/contests/abc267/tasks

G - Increasing K Times

给一个长度为n的序列A

问有多少个 对它重排的方式 p, 满足 a_[p_i], 恰好有k个相邻严格递增

范围

n 5000

2s

1024mb

我的思路

首先A的顺序无关,不妨把a排个序

然后我们只要大于关系为k个,所以不妨设末尾为0

然后考虑把相同的值看成整体

考虑每次在上次运算的基础上, 计算增加了 多个 最大值

f[前i大][j个小于关系] = 方案数

f[i][j+k] = sum f[i-1][j] * count(前i-1个)-(j+1)选k个空隙,插入p个*j+1个缝隙 插入sz(i)-p个` * sz(i)!

binom(sumf(i-1)-(j+1),k) * binom(p-1,k-1) * binom(sz(i)-p-1,j)

1
2
3
k<=sumf(i-1)-(j+1)
k<=p
j<=sz(i)-p-1

这限制关系有点多变量也多, 虽然状态是满足, 但转移代价太大

另一个就是不要多个最大值去看, 而是一个一个加入

f[前i个][j个小于关系] = 方案数

发现 当第i个 > 第i-1个时, 插入 小于关系中, 不会影响j, 插入= 和 大于关系, 会增加1

f[i][j] = f[i-1][j] * j + f[i-1][j-1] * ((i-1)-(j-1))

当第i个=第i-1个时, 插入小于关系, 或=第i个的值的后面时, 不影响j, 设[0..i-1]中有sz个和第i个相等的

f[i][j] = f[i-1][j] * (j+sz(i)) + f[i-1][j-1] * ((i-1)-(j-1)-sz(i))

似乎就没了?

代码

https://atcoder.jp/contests/abc267/submissions/35640744

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

ll read(){ll r;scanf("%lld",&r);return r;}

int a[5010];
int sz[5010];
mint f[5010][5010]; // [i][count <]

int main(){
  int n=read();
  int k=read();
  rep(i,0,n)a[i]=read();
  sort(a,a+n);
  rep(i,0,n) sz[i]=(i==0||a[i]!=a[i-1])?1:(sz[i-1]+1);
  f[0][0]=1;
  rep(i,1,n)rep(j,0,i+1){
    auto&r=f[i][j];
    r += f[i-1][j]*(j+(sz[i]-1)+1); // 在原来小于的地方,或原来=a[i]的后面,或头部 插入
    if(j) r += f[i-1][j-1] * (i-(j-1)-(sz[i]-1)); // 在原来 等于/大于 且比a[i]小的后面插入
  }
  printf("%d\n",f[n-1][k].val());
  return 0;
}

总结

G

数数题,没啥

Ex

裸题 fft + (0/1的fwt,直接暴力)

一堆2s的, 还好题目时限是4s

https://atcoder.jp/contests/abc267/submissions/35641840

参考

官方题解