海亮02/18杂题
T1
题意
给你一个长度为 \(n\) 的数列，然后给你 \(q\) 个交换或不交换操作，你可以选择操作或者不操作，问所有情况下逆序对的总和。
答案需要对 \(10 ^ 9 + 7\) 取模。
\(n\leq 3000\)，\(q\leq 3000\)。
题解
发现一个问题，对于操作执不执行很难描述，怎么办？
我们考虑设 \(f(i,j)\) 表示 \(a_i>a_j\) 的情况占总情况数的比例（其实就是看、作期望啦），然后在最后把总情况数 \(2^q\) 乘一下即可。
然后考虑每个操作对 \(f\) 的影响。
不难发现，有影响的只有 \(f(x,i)\)（当然还有 \(f(i,x)\)）和 \(f(y,i)\)（当然还有 \(f(i,y)\)）。
发现影响是 \(O(n)\) 的，直接更新即可。
然后就做完了，整道题最难的点就是第一步转化拆贡献。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool stmemory;
namespace Call_me_Eric{
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 5e3 + 10, mod = 1e9 + 7;
int n, a, b;
int f[maxn][maxn][2], sum[maxn][maxn][2];
int qpow(int x,int a){
int res = 1;
while(a){
if(a & 1){res = res * x % mod;}
x = x * x % mod;a >>= 1;
}
return res;
}
int pw[maxn], pre[maxn];
void main(){
n = read(); a = read(); b = read();if(a < b)swap(a, b);
pw[0] = 1;for(int i = 1;i < maxn;i++){pw[i] = pw[i - 1] * 2 % mod;}
pre[0] = f[0][0][0] = f[0][0][1] = sum[0][0][0] = sum[0][0][1] = 1;
int ans = 0;
for(int i = 1;i <= n;i++){
sum[i][0][1] = f[i][0][1] = (pre[i - 1] - (i - b >= 0 ? pre[i - b] : 0) + mod) % mod;
for(int j = 1;j <= i;j++){
if(j >= b){
int val = sum[i - b][j - b][0];
if(j >= a)ans = (ans + val * pw[max(n - i - 1,0ll)] % mod) % mod;
else f[i][j][1] = val;
}
}
for(int j = 1;j <= i;j++){
int val = sum[i - 1][j - 1][1];
if(j >= a)ans = (ans + val * pw[max(n - i - 1,0ll)] % mod) % mod;
else f[i][j][0] = val;
}
pre[i] = pre[i - 1];
for(int j = 1;j <= i;j++){
pre[i] = (pre[i] + f[i][j][0]) % mod;
sum[i][j][0] = (sum[i - 1][j - 1][0] + f[i][j][0]) % mod;
sum[i][j][1] = (sum[i - 1][j - 1][1] + f[i][j][1]) % mod;
}
}
printf("%lld\n",ans);
return;
}
};
bool edmemory;
signed main(){
auto stclock = clock();
Call_me_Eric::main();
auto edclock = clock();
cerr << (&stmemory - &edmemory) / 1024.0 / 1024.0 << " Mib cost.\n";
cerr << (edclock - stclock) * 1.0 / CLOCKS_PER_SEC << " Sec cost.\n";
return 0;
}