arc124_e
一种方案的权值为 \(\prod\limits_{1\leq i\leq n} b_i\)，考虑其组合意义，就是每个人在自己最终的球中选一个。
可以发现要么拿自己原来的球，要么拿上一个人传来的球。
定义状态：
\(f(i,0)\) 为第 \(i\) 个人拿自己的球，考虑前 \(i-1\) 个人的答案。
\(f(i,1)\) 为第 \(i\) 个人拿上个人的球，考虑前 \(i\) 个人的答案。
注意 \(f(i,0)\) 要受 \(i\) 传球的影响，故还不能考虑第 \(i\) 个人的答案。
转移：
定义 \(s_1(n)=\sum\limits_{1\leq i\leq n} i\)，\(s_2(n)=\sum\limits_{1\leq i\leq n} i^2\)。
\(f(i+1,0)=f(i,0) \cdot s1(a_i)+f(i,1) \cdot (a_i+1)\)。
\(s1(a_i)\) 是考虑第 \(i\) 个人
保留了多少球，后面那一坨 \((a_i+1)\) 是考虑传球的方案数。
\(f(i+1,1)=f(i,0)\sum\limits_{1\leq x\leq a_i}(x\cdot (a_i-x))+f(i,1)\cdot s1(a_i)\)。
转化一下：
\(f(i+1,1)=f(i,0)\cdot (a_i\cdot s_1(a_i)-s_2(a_i))+f(i,1)\cdot s1(a_i)\)。
两坨都是枚举传了多少球给第 \(i+1\) 个人选，只是前面要乘上第 \(i\) 个人的贡献。
dp 部分基本结束，但还有两个问题。
- 处理重复答案。
如果每个人往后传相同个数的球，就相当于没传，即只要每个人都往后面传了球，就一定会产生重复答案。
所以考虑将答案减去每个人都往后传球产生的答案。
在 \(f(i+1,0)=f(i,0) \cdot s1(a_i)+f(i,1) \cdot (a_i+1)\) 转移时将 \(a_i-1\)，即可钦定每个人必须往后传球。
- 断环为链
只需要初值 \(f_{1,0}=1\) 和 \(f_{1,1,}=1\) 分别求一次即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,p=1e9+7,inv6=166666668;
int n,a[N],f[N][2];
int s1(int n) {return n*(n+1)/2%p;}
int s2(int n) {return n*(n+1)%p*(2*n+1)%p*inv6%p;}
int calc(int op1,int op2)
{
memset(f,0,sizeof(f));
f[1][0]=op1,f[1][1]=!op1;
for(int i=1;i<=n;i++)
{
int j=i%n+1;
f[j][0]=(f[i][0]*s1(a[i]-op2)%p+f[i][1]*(a[i]+1-op2)%p)%p;
f[j][1]=(f[i][0]*((a[i]*s1(a[i])-s2(a[i]))%p+p)%p+f[i][1]*s1(a[i])%p)%p;
}
return f[1][!op1]-1;// -1 因为初值 f[1][0] or f[1][1] 赋为了 1，但这是不存在的方案，需要减去。
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
cout<<((calc(0,0)+calc(1,0)-calc(0,1)-calc(1,1))%p+p)%p;
}
P4528 [CTSC2008]图腾
参考了第一篇题解。写这篇主要是想自己重新推一遍。
规定 abcd 为 \(1\leq A < B < C < D \leq n\) 且 \(y_A,y_B,y_C,y_D\) 的排名为 \(a,b,c,d\) 的方案数。如果 abcd 中某个值为 x，则排名任意。
那么题目就是求 1324-1243-1432。
思考一下发现直接统计是不可能的，考虑有哪几种情况容易统计。
1234- 只限制了一个值的，比如
1xxx。
然后其他好像稍微难一点，但发现限制了两个值的好像也能统计。
考虑把答案拆开：
1324-1243-1432
=(1x2x-1423)-(12xx-1234)-(14xx-1423)
=1x2x-12xx-14xx+1234
=1x2x-1xxx+13xx+1234
设 \(L_i\) 为 \(i\) 左侧小于 \(y_i\) 的个数，\(R_i\) 为右侧小于 \(y_i\) 的个数，\(RR_i\) 为右侧大于 \(y_i\) 的个数。
不难发现 \(R_i=y_i-1-L_i，RR_i=n-i-R_i\)。
\(L_i\) 用树状数组维护即可。
讨论四种情况：
1x2x
枚举 2 的位置 \(i\)，右边显然有 \(RR_i\) 种选择。
设左边俩位置为 \(j,k\)，则 \(j < k < i,y_j < y_i < y_k\)。
若只考虑 \(y_j < y_i,j<i,k<i\)，则有 \(L_i \cdot (i-1)\) 种，需要减去 \(j \geq k\) 和 \(j<k,y_k < y_i\) 的情况。
\(j<k,y_k<y_i\) 的方案就是 \(C_{L_i}^{2}\)。
每个 \(j\) 对应 \(k\) 选在 \([1,j]\) 位置的时候不合法，总方案 \(\sum\limits_{1 \leq j <i,y_j < y_i} j\)。
1xxx
枚举 1 的位置 \(i\)，右边随便选 3 个比当前位置大的，\(\sum\limits C_{RR_i}^{3}\)
13xx
枚举 3 的位置 \(i\)，选 4 的方案为 \(RR_i\)。
设 1,2 位置分别为 \(j,k\)，则 \(j < i < k,y_j < y_k < y_i\)。
还是只考虑 \(y_j < y_i\)，则有 \(L_i \cdot (y_i-1)\)，需要减去 \(k \leq i,y_k<y_i\) 和 \(y_k \leq y_j\)。
\(k \leq i,y_k<y_i\) 方案还是 \(C_{L_i}^{2}\)。
每个 \(j\) 对应 k 选在 \(y \leq y_j\) 的位置时不合法，总方案 \(\sum\limits_{1 \leq j <i,y_j < y_i} y_j\)。
1234
枚举 3 的位置 \(i\)，选 4 的方案为 \(RR_i\)。
设 2 的位置为 \(j\)，则选 1 的方案为 \(L_j\)，选 1,2 的方案求个和就可以了。
由于是对 \(2^{24}\) 取模，可以考虑开无符号整型，最后再保留后 23 位。
于是就冲到了最优解
#include<bits/stdc++.h>
#define int unsigned
using namespace std;
const int N=2e5+5;
int n,ans,a[N],c[N],L[N],R[N],RR[N];
void upd(int x,int v) {for(;x<=n;x+=x&-x) c[x]+=v;}
int sum(int x) {int r=0;for(;x;x^=x&-x) r+=c[x];return r;}
int C2(int n) {return 1ll*n*(n-1)/2;}
char buf[1<<15],*p1=buf,*p2=buf;
#define nc() (p1==p2&&(p2=buf+fread(p1=buf,1,1<<15,stdin),p1==p2)?-1:*p1++)
inline int rd()
{
int x=0,f=1;char c=nc();
for(;!isdigit(c);c=nc()) if(c=='-') f=-1;
for(; isdigit(c);c=nc()) x=(x<<3)+(x<<1)+(c^48);
return x*f;
}
signed main()
{
n=rd();
for(int i=1;i<=n;i++) a[i]=rd();
for(int i=1;i<=n;i++) L[i]=sum(a[i]),R[i]=a[i]-L[i]-1,RR[i]=n-R[i]-i,upd(a[i],1);
memset(c,0,sizeof(c));upd(a[2],L[2]);
for(int i=3;i<=n;i++) ans+=sum(a[i])*RR[i],upd(a[i],L[i]); //1234
for(int i=1;i<=n;i++) ans-=1ll*RR[i]*(RR[i]-1)*(RR[i]-2)/6; // 1xxx
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++) ans+=((L[i]*(i-1)-C2(L[i])-sum(a[i]))*RR[i]),upd(a[i],i); // 1x2x
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++) ans+=(L[i]*(a[i]-1)-C2(L[i])-sum(a[i]))*RR[i],upd(a[i],a[i]); // 13xx
cout<<(ans&16777215);
}