AtCoder Beginner Contest 380

啊啊啊，这场题还蛮简单的，我都会做。但因为在 F 题犯蠢了，结果 G 都没时间看。不过看了估计也敲不完吧，还是做得太慢了）

F - Exchange Game

T 和 A 玩一个游戏，轮流把一张牌放到桌上，然后可以选择一张桌上比它小的牌拿回去，不能操作的人输。

就是一个记忆化搜索，比较蠢的是我以为放牌必须要满足桌上有比它小的牌，然后就寄了。

#include <bits/stdc++.h>
using namespace std;
const int N=5005;
int f[N][N][2];
int k;
int a[15];
int dfs(int x,int y,int op)
{
    if(~f[x][y][op]) return f[x][y][op];
    int flag;
    if(op==0)
    {
        flag=0;
        for(int i=0;i<k;i++)
            if(x>>i&1)
            {
                flag|=dfs(x-(1<<i),y,1);
                for(int j=0;j<k;j++)
                    if(a[i]>a[j]&&!((x+y)>>j&1))
                        flag|=dfs(x-(1<<i)+(1<<j),y,1);
            }
    }
    else
    {
        flag=1;
        for(int i=0;i<k;i++)
            if(y>>i&1)
            {
                flag&=dfs(x,y-(1<<i),0);
                for(int j=0;j<k;j++)
                    if(a[i]>a[j]&&!((x+y)>>j&1))
                        flag&=dfs(x,y-(1<<i)+(1<<j),0);
            }    
    }
    return f[x][y][op]=flag;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(f,-1,sizeof(f));
    int n,m,l;cin>>n>>m>>l;
    k=n+m+l;
    for(int i=0;i<k;i++) cin>>a[i];
    cout<<(dfs((1<<n)-1,(1<<(n+m))-(1<<n),0)?"Takahashi":"Aoki")<<'\n';
    return 0;
}

G - Another Shuffle Window

有一个排列 $P$ 和整数 $k$。在 $1$ 到 $n-k+1$ 中随机选择一个 $i$，然后随机打乱 $P_i,P_{i+1},\cdots,P_{i+k-1}$。求逆序对个数期望。

滑动窗口。把序列拆成 窗口左边，窗口，窗口右边 三部分，维护窗口滑动时窗口内和窗口之间的逆序对个数。可以对三部分分别维护一颗权值线段树，然后考虑 $P_i$ 和 $P_{i+k}$ 的影响即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
const int p=998244353;
int tr[3][4*N];
void pushup(int p,int* tr)
{
    tr[p]=tr[p*2]+tr[p*2+1];
}
void update(int x,int k,int l,int r,int p,int* tr)
{
    if(l==r)
    {
        tr[p]+=k;
        return;
    }
    int m=(l+r)>>1;
    if(x<=m) update(x,k,l,m,p*2,tr);
    else update(x,k,m+1,r,p*2+1,tr);
    pushup(p,tr);
}
int query(int ql,int qr,int l,int r,int p,int *tr)
{
    if(ql<=l&&qr>=r)
        return tr[p];
    int m=(l+r)>>1;
    int ans=0;
    if(ql<=m) ans+=query(ql,qr,l,m,p*2,tr);
    if(qr>m) ans+=query(ql,qr,m+1,r,p*2+1,tr);
    return ans;
}
int a[N];
ll fac[N],ifac[N];
ll fpow(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
const int inv2=fpow(2,p-2);
void init()
{
    fac[0]=1;
    for(int i=1;i<N;i++) fac[i]=i*fac[i-1]%p;
    ifac[N-1]=fpow(fac[N-1],p-2);
    for(int i=N-1;i;i--) ifac[i-1]=i*ifac[i]%p;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=k;i++) update(a[i],1,1,n,1,tr[1]);
    ll cur=0;
    for(int i=k+1;i<=n;i++) 
    {
        cur=(cur+query(a[i],n,1,n,1,tr[2]))%p;
        update(a[i],1,1,n,1,tr[2]);
    }
    for(int i=1;i<=k;i++) cur=(cur+query(1,a[i],1,n,1,tr[2]))%p;
    cur=(cur+1ll*k*(k-1)/2%p*inv2)%p;
    ll ans=cur*fac[k]%p;
    for(int i=1;i<n-k+1;i++)
    {
        cur=(cur-query(a[i+k],n,1,n,1,tr[0])+p)%p;
        cur=(cur+query(a[i],n,1,n,1,tr[0]))%p;
        cur=(cur-query(a[i],n,1,n,1,tr[0])+p)%p;
        cur=(cur-query(1,a[i],1,n,1,tr[2])+p)%p;
        cur=(cur-query(a[i+k],n,1,n,1,tr[1])+p)%p;
        update(a[i],1,1,n,1,tr[0]),update(a[i],-1,1,n,1,tr[1]);
        update(a[i+k],1,1,n,1,tr[1]),update(a[i+k],-1,1,n,1,tr[2]);
        cur=(cur-query(1,a[i+k],1,n,1,tr[2])+p)%p;
        cur=(cur+query(1,a[i],1,n,1,tr[2]))%p;
        cur=(cur+query(1,a[i],1,n,1,tr[1]))%p;
        cur=(cur+query(a[i+k],n,1,n,1,tr[0]))%p;
        cur=(cur+query(1,a[i+k],1,n,1,tr[2]))%p;
        ans=(ans+cur*fac[k])%p;
    }
    ans=ans*fpow(n-k+1,p-2)%p*ifac[k]%p;
    cout<<ans<<'\n';
    return 0;
}