ZigZagK的博客
[思维+树状数组]ACL Contest 1E【Shuffle Window】题解
[思维+树状数组]ACL Contest 1E【Shuffle Window】题解
2020年9月29日 15:56
AtCoder
查看标签

题目概述

ACL Contest 1E

解题报告

神仙转化题我根本做不来……我又来翻译题解了。

按顺序random_shuffle可以转化为以下形式:

  • 有一个数组 $A$ ,刚开始有排列 $p$ 中 $[1,K]$ 的元素,还有一个空的数组 $B$ 。
  • 第 $i$ 次操作时,从 $A$ 中随机选出一个元素插入 $B$ 中。
  • 第 $i$ 次操作后,如果 $p_{i+K}$ 存在,则将 $p_{i+K}$ 加入 $A$ 中。
  • 求最后数组 $B$ 中的逆序对个数。

感性理解一下这种方式和原来的方式效果是一样的。我们定义 $f(i)=\max\{i-K,0\}$ 表示 $i$ 加入 $A$ 的时间。

那么我们考虑 $i$ 和 $j$ 产生逆序对的情况( $i<j$ ):

  • $p_i<p_j$ ,那么 $i,j$ 必须交换过位置,前提条件是 $i,j$ 同时出现在了 $A$ 数组中。

    令 $p={K-1\over K}$ ,由于 $i$ 在 $j$ 加入之前一直在 $A$ 中,因此概率为 $p^{f(j)-f(i)}$ 。

    $i,j$ 同时出现在 $A$ 之后,显然 $i,j$ 交换位置的概率为 $1\over 2$ 。

    因此概率为 $p^{f(j)-f(i)}\over 2$ 。

  • $p_i>p_j$ ,那么 $i,j$ 没有交换过位置,显然概率为 $1-{p^{f(j)-f(i)}\over 2}$ 。

所以用树状数组维护就行了。

示例程序

  • 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
#include<cstdio> using namespace std; typedef long long LL; const int maxn=200000,MOD=998244353,INV2=MOD+1>>1; int n,K,a[maxn+5],ans; int pw[maxn+5],INV[maxn+5],c[2][maxn+5]; #define ADD(x,y) (((x)+(y))%MOD) #define MUL(x,y) ((LL)(x)*(y)%MOD) int Pow(int w,int b) {int s=1;while (b) {if (b&1) s=MUL(s,w);w=MUL(w,w);b>>=1;}return s;} void Insert(int *c,int x,int y) {for (int i=x;i<=n;i+=i&-i) c[i]=ADD(c[i],y);} int Sum(int *c,int x) {int sum=0;for (int i=x;i;i-=i&-i) sum=ADD(sum,c[i]);return sum;} int main(){ scanf("%d%d",&n,&K);int p=MUL(K-1,Pow(K,MOD-2)); pw[0]=1;for (int i=1;i<=n;i++) pw[i]=MUL(pw[i-1],p); p=Pow(p,MOD-2);INV[0]=1;for (int i=1;i<=n;i++) INV[i]=MUL(INV[i-1],p); for (int i=1,x;i<=n;i++){ scanf("%d",&x); int F=i>K?i-K:0,pre=Sum(c[1],x-1),suf=ADD(Sum(c[1],n),MOD-Sum(c[1],x)); ans=ADD(ans,Sum(c[0],n)-Sum(c[0],x)); ans=ADD(ans,MOD-MUL(pw[F],suf)); ans=ADD(ans,MUL(pw[F],pre)); Insert(c[0],x,1);Insert(c[1],x,MUL(INV[F],INV2)); } printf("%d\n",ans);return 0; }
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
本文写于 1645 天前,最后更新于 1645 天前。
部分信息可能已经过时,博主也可能已经无法对其内容进行解答。
OK
  1. 1 Skyscape Plum - Melodic Artist
  2. 2 ほしのおとしもの ああああ
  3. 3 感情の摩天楼 ~ Cosmic Mind 上海アリス幻樂団
  4. 4 秘匿されたフォーシーズンズ 上海アリス幻樂団
  5. 5 Ideal and the Real 小西利樹
  6. 6 Undertale Toby Fox
  7. 7 First Steps Lena Raine
  8. 8 Mirror Temple (Mirror Magic Mix) Lena Raine / 2 Mello
  9. 9 City of Tears Christopher Larkin
  10. 10 Tower Of Heaven (You Are Slaves) Feint
Skyscape - Plum - Melodic Artist
00:00 / 00:00
An audio error has occurred, player will skip forward in 2 seconds.

作曲 : Jeong Min Jae

纯音乐,请欣赏