T2 AGC034F RNG and XOR
给定 n 和一个长度为 (2^n) 的数组 A (从 0 标号).
有一个初始为 0 的变量 x . 不断操作, 每次操作以 (frac {A_i}{sum_{j=0}^{2^n-1} A_j}) 的概率将 x 变成 x xor i .
对于所有 i∈[0,2n) , 求出 x 第一次变成 i 的期望操作次数.
n⩽18,1⩽A⩽1000
先转化一下，(f[i]) 表示i变成0的期望步数。（(i >= 1)）
(large f[i] = 1 + sum f[i xor j] imes p[j])
(large ?? + sum_{i=1}^n (f[i] - 1) = sum sum f[i xor j] imes p[j])
由于 (sum p = 1) 所以可以知道 $ ?? = f[0] + 2 ^ n - 1$
((f[0] , f[1] , f[2] , ... , f[2^n-1]) * (p[0] , p[1] , p[2] , ... , p[2 ^n-1]) = (f[0] + 2^n - 1 , f[1] - 1 , f[2] - 1 , ... , f[2^n-1]-1))
给 p[0] 减个1
((f[0] , f[1] , f[2] , ... , f[2^n-1]) * (p[0] - 1 , p[1] , p[2] , ... , p[2 ^n-1]) = (2^n - 1 , -1 , -1 , ... , -1))
做一遍FWT即可。 最后有个玄学的地方 f[0] 可能不等与 0 ， 要让所有的f都减去一个 f[0]
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long LL;
const int N = 1<<18|1 , mod = 998244353 , G = 3 , Ginv = (mod + 1) / 3 , inv2 = (mod + 1) / 2;
inline int read()
{
register int x = 0 , f = 0; register char c = getchar();
while(c < '0' || c > '9') f |= c == '-' , c = getchar();
while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0' , c = getchar();
return f ? -x : x;
}
int n , len;
int p[N] , q[N] , F[N];
inline int add(int a , int b) { a += b; return a >= mod ? a - mod : a; }
inline int mul(int a , int b) { return (LL)a * b % mod; }
inline int ksm(int a , int k) { int ans = 1; a %= mod; for( ; k ; k >>= 1 , a = mul(a , a)) if(k & 1) ans = mul(ans , a); return ans; }
void FWT(int *A , int opt)
{
for(int mid = 1 ; mid < len ; mid <<= 1)
{
int siz = mid << 1;
for(int j = 0 ; j < len ; j += siz)
{
for(int k = 0 ; k < mid ; ++k)
{
int a = A[j + k] , b = A[j + k + mid];
if(opt == 1)
A[j + k] = add(a , b) , A[j + k + mid] = add(a , mod - b);
else
A[j + k] = mul(inv2 , add(a , b)) , A[j + k + mid] = mul(inv2 , add(a , mod - b));
}
}
}
return ;
}
int main()
{
n = read(); len = 1 << n; int sum = 0;
for(int i = 0 ; i < len ; ++i) sum += (p[i] = read());
sum = ksm(sum , mod - 2);
for(int i = 0 ; i < len ; ++i) p[i] = mul(p[i] , sum);
for(int i = 1 ; i < len ; ++i) q[i] = mod - 1;
q[0] = len - 1; p[0] = add(p[0] , mod - 1);
FWT(q , 1); FWT(p , 1);
for(int i = 1 ; i < len ; ++i) F[i] = mul(q[i] , ksm(p[i] , mod - 2));
FWT(F , -1);
int tmp = mod - F[0];
for(int i = 0 ; i < len ; ++i) cout << add(tmp , F[i]) << '
';
return 0;
}
T3 AT4513 [AGC030D] Inversion Sum
题目大意: 给你一个长度为n的数列，然后给你q个交换或不交换操作，你可以选择操作或者不操作，问所有情况下逆序对的总和。
数据范围: n<=3e3 , q<=3e3
期望dp，
先转成期望，再乘上总的情况，设(dp[i][j]) 表示 (i > j) 的概率，然后具体的转移看代码。。。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long LL;
const int N = 3010 , mod = 1e9+7 , inv2 = (mod + 1) / 2;
inline int read()
{
register int x = 0 , f = 0; register char c = getchar();
while(c < '0' || c > '9') f |= c == '-' , c = getchar();
while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0' , c = getchar();
return f ? -x : x;
}
int n , Q;
int a[N] , F[N][N] , G[N][N];
inline int add(int a , int b) { return a + b >= mod ? a - mod + b : a + b; }
inline int mul(int a , int b) { return (LL)a * b % mod; }
int main()
{
n = read(); Q = read();
for(int i = 1 ; i <= n ; ++i) a[i] = read();
for(int i = 1 ; i <= n ; ++i) for(int j = 1 ; j <= n ; ++j) F[i][j] = a[i] > a[j];
int p1 , p2 , res = 1;
while(Q--)
{
p1 = read(); p2 = read();
for(int i = 1 ; i <= n ; ++i) if(i != p1 && i != p2)
{
G[i][p1] = G[i][p2] = mul(inv2 , add(F[i][p1] , F[i][p2]));
G[p1][i] = G[p2][i] = mul(inv2 , add(F[p1][i] , F[p2][i]));
}
for(int i = 1 ; i <= n ; ++i) if(i != p1 && i != p2) F[i][p1] = G[i][p1] , F[i][p2] = G[i][p2] , F[p1][i] = G[p1][i] , F[p2][i] = G[p2][i];
F[p1][p2] = F[p2][p1] = mul(inv2 , add(F[p1][p2] , F[p2][p1]));
res = mul(res , 2);
}
int ans = 0;
for(int i = 1 ; i <= n ; ++i) for(int j = i + 1 ; j <= n ; ++j) ans = add(ans , F[i][j]);
cout << mul(res , ans) << '
';
return 0;
}