Atcoder abc330

發表於 更新於 分類於 ， Disqus： 文章字數： 3.1k 所需閱讀時間 ≈ 10 分鐘
G(计数，分类讨论)

https://atcoder.jp/contests/abc330

G - Inversion Squared

a[n]

$a[i] \in [1,n]$ 或$a[i]=-1$, 1~n最多出现一次

-1能替换成$[1\cdots n]$中的数

求 所有 ((a能产生的$1\dots n$排列)的逆序对的个数)的平方和，mod 998244353

n = 3000

2s

1024mb

我的思路

题面很质朴，n 3000说明可能n^2一类的算法

令x=-1的个数

对于非-1的部分可以直接算出，然后乘上 (x)! 就是贡献了

对于-1和-1之间，要知道每一个 排列的方案，交换这两个位置 对应的也是一个方案，而这两个方案之间 一个贡献1,一个贡献0

所以 是 $x!\frac{(x-1)x}{2}\cdot \frac{1}{2}$, 分别是 总方案数，配对位置数，和1/2的平均贡献

那么这个问题来到的就是 -1和给定值之间的逆序对 的贡献个数了

contribute[有值pos1] = f_left(value,left -1 count) + f_right(value, right -1 count)

所以 如果能 计算出

$f(value,cnt)=$ 在一共x个-1的情况下，左侧-1的位置有cnt个，当前值是value,的方案数

l[v] = 比v小的未填的值的个数

那么左侧的贡献为 $cnt\star (x-l[value]) (x-1)!$

右侧的贡献为 = $(x-cnt)\star lvalue!$

似乎就没了吧？

xxxxxxxxxxxxxxxxxx上面读错题目了， 要逆序对个数 的平方和，不只是逆序对的个数和

已经填好的逆序对=C，-1内部的逆序对=A，-1和填好的逆序对=B

$(C+A+B)^2=C^2+A^2+B^2+2AB+2BC+2CA$

首先C是不变的，A,B是根据填写情况变化的

所以这里的$C^2+2BC+2CA$很好算，和上面一样，

那问题来到$A^2,B^2,2AB$怎么算

一个想法是和上面一样，考虑两个位置交换会对贡献有什么影响

显然一样的， 交换2个位置，那么它们的A相差为1,问题是B是可能变化的，且变化无法确定

A^2 也有办法，因为A^2相当于x个数的全排列的 逆序对平方和

1
2
3
4
len=1:0
len=2:0 [1]
len=3:0  1 [1  2][2  3]
len=4:0  1  1  2  2  3 [1  2  2  3  3  4][2  3  3  4  4  5][3  4  4  5  5  6]

个数上可以 生成函数表示

$f_0(x)=1$

$f_1(x)=1+x=(1+x)f_0(x)$

$f_2(x)=1+2x+2x^2+x^3=(1+x+x^2)f_1(x)$

$f_3(x)=(1+x+x^2+x^3)f_2(x)$

这个 采取 分治的方法计算 $O(n^2 \log n)$ 可以算出来，但是 $2^{23} =8388608 > 4498500=\frac{2999\cdot 3000}{2}$ 这会炸掉吗？

然而这个思路带来的一个新的启发能否用 生成函数的方法 直接计算出每个逆序对的方案数，

例如 $f_3(x)=(1+x+x^2+x^3)f_2(x)$ 中$x^2$是 在说 对于后缀长度$4$的4个数字，第一个是其中第2+1小的（因为1-index所以+1),

想了想，好像并不行，虽然在-1的位置填入值的时候，可以计算和后面相比多少个，但是这里产生的分叉状态没法合并，意味着分叉的状态数量会影响时间空间复杂度

题解

意义转化，abc277g ！！！！！补过的，又忘了

就是 (逆序对平方) = 逆序对 x 逆序对= sum 四元组(l0,r0,l1,r1)满足 (l0 < r0,l1< r1,a[l0] > a[r0],a[l1] > a[r1]) 统计

q=未决定的个数

分类

  • A: (l,r) 固定， a=好的pair个数，我们也只需要考虑好的个数
  • B: (l,r) 其中一个固定
  • C: (l,r) 都没固定，c=pair个数=$\binom{q}{2}$

因此 (l0,r0,l1,r1) 有

  • (A,A)
  • (B,B)
  • (C,C)
  • 2*(A,C)
  • 2*(B,C)
  • 2*(A,B)

（A,A): $a^2q!$ 显然

(A,B)(B,A):

  • (i,q)
  • (q,i)
1
2
3
for i in 已经确定的 位置:
	ans += i 左 边的未确定位置个数 * 比a[i] 大 的未使用值的个数 * a * 2
	ans += i 右 边的未确定位置个数 * 比a[i] 小 的未使用值的个数 * a * 2

(A,C)(C,A):

$a\frac{cq!}{2}\cdot 2$ 对于每个排列，的指定两个-1的位置，该排列和交换这两个位置的排列，有且只有一个产逆序对，所以$\frac{1}{2}$ 因为计数2次所以还是要再乘上2

(C,C):

  • (l0,r0)=(l1,r1): $\frac{cq!}{2}$
  • l0=l1 and r0!=r1,l0!=l1 and r0==r1,一样的指定3个位置，看平均产出率$\displaystyle \frac{\binom{q}{3}q!}{3}\cdot 2\cdot 2$, 乘上2是因为r0,r1可以交换,另一个2是方案对称
  • l0<r0=l1<r1,l1 < r1 = l0 < r0:一样的指定3个位置，看平均产出率$\displaystyle \frac{\binom{q}{3}q!}{6}\cdot 2$, 乘上2是2是方案对称
  • 4个坐标都不一样,一样$\binom{q}{4}q!\frac{6}{4!}\cdot 6$，选择位置，所有排列，产出率，和6种 下标关系

(B,C),(C,B):

先确定b,再看c

  • 没有共用位置，$B确定 \star \binom{q-1}{2} (q-1)! \frac{1}{2}\cdot 2$
  • 有共用位置
    • b=(i,p),c=(p,q)贡献 $\displaystyle \binom{q-g[a[i]]}{2}\binom{gp[i]}{2}(q-2)!\cdot 2$, 值更小，坐标更大
    • b=(i,p),c=(q,p)贡献 $\displaystyle ((q-gp[i])+\cdots+(q-1))(g[a[i]]+\cdots+(q-1))(q-2)!\cdot 2$,
    • b=(p,i),c=(p,q)贡献 $\displaystyle (gp[i]+\cdots+(q-1))((q-g[a[i]])+\cdots+(q-1))(q-2)!\cdot 2$,
    • b=(p,i),c=(q,p)贡献 $\displaystyle \binom{g[a[i]]}{2}\binom{q-gp[i]}{2}(q-2)!\cdot 2$,

(B,B):

  • (i,p)(i,p):$gpi(q-1)!$
  • (i,p)(i,q):$\displaystyle A_2^{gp[i]}A_2^{(q-g[a[i]])}(q-2)!$
  • (p,i)(i,q):$gpi(q-g[a[i]])(g[a[i]])(q-2)!$
  • (p,i)(p,i):$(q-gp[i])ga[i]!$
  • (p,i)(q,i):$\displaystyle A_2^{q-gp[i]}A_2^{g[a[i]]}(q-2)!$

i < j, 也只有这里需要n^2,上面都是O(n)以内就能算的, 见代码

  • (i,p)(j,p)

  • (p,i)(p,j)

  • (i,p)(p,j)

  • (i,p)(j,q)

  • (p,i)(q,j)

  • (p,i)(j,q)

    • a[i] > a[j]
    • a[i] < a[j] < a[p]
    • a[j] > a[p] > a[i]

  • (i,p)(q,j)

    • 讨论坐标
      • i < p < j
      • i < j < p
    • 讨论值
      • a[j] > a[i]
      • a[i] > a[p] > a[j]
      • a[i] > a[j] > a[p]

也就AA(1)+AB(2)+AC(1)+CC(4)+BC(6)+BB(18) = 32种情况，讨论吐了150行

代码

https://atcoder.jp/contests/abc330/submissions/50047211

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <bits/stdc++.h>
#include <atcoder/modint>
const int MOD=998244353;
using mint = atcoder::static_modint<MOD>;
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
#define per(i,a,n) for (ll i=n;i-->(ll)(a);)
ll read(){ll r;scanf("%lld",&r);return r;}

const int N=3000;
int a[N+10];
bool exist[N+10]; // v[i] = i出现过
int l[N+10]; // l[value] = 比l小的 未填的个数
int lp[N+10]; // lp[idx] = 比idx小的 未填位置的个数
mint fac[N+10]={1};
mint ifac[N+10];
mint inv[N+10];
mint binom(int n,int m){ return (m > n or m < 0)?0: fac[n]*ifac[m]*ifac[n-m]; }
mint sum(ll a,ll b) { return (a > b)?0: (a+b)*(b-a+1)/2; }

int main(){
  rep(i,1,N+1) fac[i]=fac[i-1]*i;
  ifac[N]=fac[N].inv();
  per(i,0,N) ifac[i]=ifac[i+1]*(i+1);
  rep(i,1,N) inv[i] = ifac[i]*fac[i-1];
  int n=read();
  rep(i,1,n+1) a[i]=read();
  rep(i,1,n+1) if(a[i]!=-1) exist[a[i]]=1;
  ll x=0; // -1的个数
  rep(i,1,n+1) x+=a[i]==-1;
  // 计算比
  int cnt = 0;
  rep(v,1,n+1) {
    if(!exist[v]) cnt++;
    else l[v] = cnt;
  }
  cnt = 0;
  rep(i,1,n+1) {
    if(a[i] == -1) cnt++;
    else lp[i] = cnt;
  }
  mint ans = 0;
  // (l0,r0,l1,r1)
  // A 2个确定, A=逆序对个数
  mint A = 0;
  rep(i,1,n+1) if(a[i] != -1) rep(j,i+1,n+1) if(a[j] != -1 and a[j] < a[i]) A++;
  // B 1个确定
  // C 0个确定

  // (A,A)
  ans += A*A*fac[x];

  // (A,B),(B,A)
  rep(i,1,n+1) if(a[i] != -1) {
    // (p,i) A
    ans+=lp[i]*(x-l[a[i]])*fac[x-1]*A*2; // 左侧位置,更大值,剩余随便放, 对称x2
    // (i,p) A
    ans+=(x-lp[i])*l[a[i]]*fac[x-1]*A*2; // 右侧位置,更小值,剩余随便放, 对称x2
  }

  // (A,C),(C,A)
  ans += fac[x]*binom(x,2)*inv[2]*A*2; // 所有排列，选2个位置，1/2产出率，A的方案，对称

  // (C,C)
  //    (l0,r0) == (l1,r1)
  ans += fac[x]*binom(x,2)*inv[2]; // 所有排列，选2个位置，1/2产出率
  //    l0 == l1, or  r0 == r1
  ans += fac[x]*binom(x,3)*inv[3]*2*2;// 选3个位置(p0,p1,p0,p2)，1/3产出率,p1和p2交换,前组和后组交换
  //    l0 < r0 = l1 < r1, l1 < r1 = l0 < r0
  ans += fac[x]*binom(x,3)*inv[6]*2;// 选3个位置(p0,p1,p1,p2)，1/6产出率, 前组和后组交换
  //    4个坐标都不一样
  ans += fac[x]*binom(x,4)*6*ifac[4]*6;// 选4个位置(p0,p1,p2,p3)，6/4!产出率, 6种p的交换

  // (B,C),(C,B), 固定的下标i,未固定的下标p,q,l
  rep(i,1,n+1) if(a[i] != -1) {
    // 互不相同
    // (p,i) (q,l)
    ans+=lp[i]*(x-l[a[i]])*fac[x-1]*binom(x-1,2)*inv[2]*2;//左侧,更大值,剩余排列,选2个位置,1/2产出率,对称x2
    // (i,p) (q,l)
    ans+=(x-lp[i])*l[a[i]]*fac[x-1]*binom(x-1,2)*inv[2]*2;//右侧,更小值,剩余排列,选2个位置,1/2产出率,对称x2
    // 有共用下标
    // (p,i) (p,l)
    ans+=sum(x-lp[i],x-1)*sum(l[a[i]],x-1)*fac[x-2]*2;//p,l下标枚举,值枚举,剩余排列,对称x2
    // (i,p) (l,p)
    ans+=sum(lp[i],x-1)*sum(x-l[a[i]],x-1)*fac[x-2]*2;//p,l下标枚举,值枚举,剩余排列,对称x2
    // (p,i) (l,p)
    ans+=binom(lp[i],2)*binom(x-l[a[i]],2)*fac[x-2]*2;//更小下标x2,更大值x2,剩余排列,对称x2
    // (i,p) (p,l)
    ans+=binom(x-lp[i],2)*binom(l[a[i]],2)*fac[x-2]*2;//更大下标x2,更小值x2,剩余排列,对称x2
  }

  // (B,B)
  rep(i,1,n+1) if(a[i] != -1) {
    // (i,p),(i,p)
    ans+=(x-lp[i])*(l[a[i]])*fac[x-1];//更大下标x1,更小值x1,剩余排列
    // (p,i),(p,i)
    ans+=(lp[i])*(x-l[a[i]])*fac[x-1];//更小下标x1,更大值x1,剩余排列
    // (i,p),(i,q)
    ans+=binom(x-lp[i],2)*binom(l[a[i]],2)*fac[x-2]*4;//更大下标x2,更小值x2,剩余排列,下标和值交换x4
    // (p,i),(q,i)
    ans+=binom(lp[i],2)*binom(x-l[a[i]],2)*fac[x-2]*4;//更小下标x2,更大值x2,剩余排列,下标和值交换x4
    // (p,i,i,q), (i,p,q,i)
    ans+=lp[i]*(x-lp[i])*l[a[i]]*(x-l[a[i]])*fac[x-2]*2;//小下标,大下标,大值,小值,剩余排列,对称x2
  }
  rep(i,1,n+1) if(a[i] != -1) rep(j,i+1,n+1) if(a[j] != -1) { // i < j, O(n^2)
    // (i,p,j,p) 更大坐标，更小值，剩余排列，交换ij
    ans+=(x-lp[j])*l[min(a[i],a[j])]*fac[x-1]*2;
    // (p,i,p,j) 更小坐标，更大值，剩余排列，交换ij
    ans+=lp[i]*(x-l[max(a[i],a[j])])*fac[x-1]*2;
    // (i,p,p,j) 更小坐标，更大值，剩余排列，交换ij
    ans+=(lp[j]-lp[i])*max(0,l[a[i]]-l[a[j]])*fac[x-1]*2;

    // (i,p,j,q) 选>j,选>i,选小值,再选大值,剩余排列,交换
    ans+=(x-lp[j])*(x-lp[i]-1)*(l[min(a[i],a[j])])*(l[max(a[i],a[j])]-1)*fac[x-2]*2;
    // (p,i,q,j) 选<i,选<j,选大值,再选小值,剩余排列,交换
    ans+=(lp[i])*(lp[j]-1)*(x-l[max(a[i],a[j])])*(x-l[min(a[i],a[j])]-1)*fac[x-2]*2;
    // (p,i,j,q) <i,>j,
    mint posmul = (lp[i])*(x-lp[j]);
    if(a[i] > a[j]) { // a[p] > a[i] > a[j] > a[q]
      ans+=posmul*(x-l[a[i]])*(l[a[j]])*fac[x-2]*2;
    }else { // a[p] > a[i], a[i] < a[j], a[j] > a[q]
      // a[p] > a[j]
      ans+=posmul*(x-l[a[j]])*(l[a[j]])*fac[x-2]*2;
      // a[j] > a[p] > a[i]
      ans+=posmul*(l[a[j]]-l[a[i]])*(l[a[j]]-1)*fac[x-2]*2;
    }
    // (i<p,q<j), a[i] > a[p], a[q] > a[j]
    posmul = 0;
    posmul += (lp[j]-lp[i])*(lp[j]-1); //    i < p < j, q < j
    posmul += (x-lp[j])*(lp[j]);       //    i < j < p, q < j
    if(a[j] > a[i]){ // a[q] > a[j] > a[i] > a[p]
      ans+=posmul*(l[a[i]])*(x-l[a[j]])*fac[x-2]*2;
    }else{ // a[i] > a[j]
      // a[i] > a[p] > a[j]
      ans+=posmul*(l[a[i]]-l[a[j]])*(x-l[a[j]]-1)*fac[x-2]*2;
      // a[i] > a[j] > a[p]
      ans+=posmul*(l[a[j]])*(x-l[a[j]])*fac[x-2]*2;
    }
  }
  printf("%d\n",ans.val());
  return 0;
}

参考

https://atcoder.jp/contests/abc330/editorial/7765

总结

哎 我就觉得做过 这个 abc277g, arc157c

就是意义转化，应该是第二次遇到了，没想出具体转化好蠢啊我，

后面的推理到没啥难度了？？？？,是亿点的很多体力活，哎abc277g