ABC380F. Exchange Game
因为 \(n+m+k\leq 12\)，考虑状压 dp，设 \(f(x,s1,s2,s3)\) 表示 先手，后手，桌子上的牌分别是哪一些，这有 \(O(3^n)\) 种状态。
然后只要枚举出哪一张即可，有
- \(f(s1,s2,s3)\to f(s2,s1-i+j,s3+i-j)(i\in s1,j\in s3,a_j<a_i)\)
- \(f(s1,s2,s3)\to f(s2,s1-i,s3+i)(i\in s1)\)
其中 \(x\to y\) 表示 \(y:=y\operatorname{or}\lnot x\)。
如果直接 map 记录，复杂度 \(O(n^33^n)\)，可以过但是不够快。
只要预处理出 \(s=(S)_2\) 在三进制表示的值 \(h_s=(S)_3\) 即可。
那么 \(f(s1,s2,s3)=g(h_{s2}+2h_{s3})\)，复杂度 \(O(n^23^n)\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 12, M = 6e5;
int a[N], n;
int f[M], pw[N], ss[1 << N];
inline int get(int s1, int s2, int s3) { return ss[s2] + ss[s3] * 2; }
bool dfs(int s1, int s2, int s3)
{
if(!s1) return 0;
int S = get(s1, s2, s3);
if(f[S] != -1) return f[S];
bool ok = 0;
for(int i = 0; i < n; i ++)
if((s1 >> i) & 1)
{
for(int j = 0; j < n; j ++)
if(a[j] < a[i] && ((s3 >> j) & 1))
ok |= !dfs(s2, s1 ^ (1 << i) ^ (1 << j), s3 ^ (1 << i) ^ (1 << j));
ok |= !dfs(s2, s1 ^ (1 << i), s3 ^ (1 << i));
}
return f[S] = ok;
}
signed main()
{
pw[0] = 1; for(int i = 1; i < N; i ++) pw[i] = pw[i - 1] * 3;
for(int i = 0; i < (1 << N); i ++)
for(int j = 0; j < N; j ++)
ss[i] += pw[j] * ((i >> j) & 1);
ios::sync_with_stdio(0);cin.tie(0);
int x, y, z; cin >> x >> y >> z;
n = x + y + z;
for(int i = 0; i < n; i ++) cin >> a[i];
int s1 = 0, s2 = 0, s3 = 0;
s1 = (1 << x) - 1;
s2 = (1 << y) - 1;
s3 = (1 << z) - 1;
s2 <<= x;
s3 <<= x + y;
memset(f, -1, sizeof f);
if(dfs(s1, s2, s3))
cout << "Takahashi";
else cout << "Aoki";
return 0;
}
ABC380G. Another Shuffle Window
考虑怎么快速计算任意 \(i\) 下的逆序对期望。把排列分割成 \([1,i)[i,i+k)[i+k,n]\) 三段。记为 \([1][2][3]\)，把整个排列记为 \(p\)。
答案即为 \(E(1,1)+E(1,2)+E(1,3)+E(2,3)+E(3,3)+Ek\)。
其中 \(E(x,y)\) 表示 \(x\) 和 \(y\) 构成的逆序对数，\(Ek\) 表示长为 \(k\) 的排列的期望逆序对数，有 \(Ek=\dfrac{k(k-1)}{4}\)。
考虑稍微容斥一下：
\[\begin{aligned} Ans&=(E(1,1)+E(1,2)+E(1,3))+(E(1,3)+E(2,3)+E(3,3))-E(1,3)+Ek\\ &=E(1,p)+E(p,3)+Ek-E(1,3) \end{aligned} \]然后预处理 \(2n\) 个 \(E(p,x),E(x,p)\),现在的问题是求 \(E(1,3)\)。
发现在从左到右增加 \(i\) 的过程中，可以通过两个树状数组维护 \([1][3]\) 里的值，然后直接做查询即可。
复杂度 \(O(n\log n)\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5, p = 998244353;
int n, a[N], k, pre[N], suf[N];
ll sp[N], ss[N];
constexpr ll qpow(ll a, ll b)
{
if(!b) return 1;
return ((b & 1) ? a : 1ll) * qpow(a * a % p, b >> 1) % p;
}
constexpr ll inv4 = qpow(4, p - 2);
struct BIT {
int a[N];
void upd(int q, int v) {for(int i = q; i < N; i += (i & -i)) a[i] += v;}
int qry(int q) {int ans = 0; for(int i = q; i; i -= (i & -i)) ans += a[i]; return ans; }
int qry(int ql, int qr) {return qry(qr) - qry(ql - 1);}
} t, t2;
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= n; i ++)
{
pre[i] = t.qry(a[i] + 1, n);
t.upd(a[i], 1);
sp[i] = (sp[i - 1] + pre[i]) % p;
}
memset(t.a, 0, sizeof t.a);
for(int i = n; i >= 1; i --)
{
suf[i] = t.qry(1, a[i] - 1);
t.upd(a[i], 1);
ss[i] = (ss[i + 1] + suf[i]) % p;
}
memset(t.a, 0, sizeof t.a);
for(int i = k; i <= n; i ++)
t.upd(a[i], 1);
ll ans = 0, Erev = 1ll * k * (k - 1) % p * inv4 % p;
ll now = 0;
for(int i = 1; i <= n - k + 1; i ++)
{
ll res = 0;
res += ss[1] - ss[i];
res += sp[n] - sp[i + k - 1];
t.upd(a[i + k - 1], -1);
now -= t2.qry(a[i + k - 1] + 1, n);
if(a[i - 1] > 1) now += t.qry(1, a[i - 1] - 1);
if(i > 1) t2.upd(a[i - 1], 1);
res -= now;
res += Erev;
ans = (ans + res) % p;
}
cout << (ans * qpow(n - k + 1, p - 2) % p + p) % p;
return 0;
}