保龄力！！！！
我是A题
有点思维难度。
Part1
观察数据，发现每一个三元组必然是 \((A,y,z) 或 (x,B,z) 或(x,y,C) 或(A,B,z)\) 的形式，可以在这上面下文章。
考虑把每个三元组想象成一个长方体，每个长方体之间会有重叠，最后求的是不规则物体的体积。
把第三维当做高度，也就是 \(z\) ,我们一层一层的求。
Part2
我们发现,如果不考虑 \((x,y,C)\) 的三元组，最后每一层的横截面一定是一个长方形截去一个长方形的图案，设为图形 \(S\)。如果只考虑 \((x,y,C)\) 的三元组，最后的横截面一定是一个阶梯形,设为图形 \(T\)。
我们分开考虑，那每一层就只受一个 每一层不同的 \(S\)，和所有层相同的 \(T\) 影响，两个图形叠加就是答案。这两个图形都可以通过后缀最大值维护。
复杂度 \(\Theta(N+A+B+C)\) ,需要用 $ int128 $
点击查看代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>#define lint __int128using namespace std;const int N=3e7+10;
typedef unsigned long long ull;inline lint read() {lint x=0;char ch=getchar();while(ch>'9' || ch<'0') {ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return x;
}void write(lint x) {if(x<0)x=-x,putchar('-');if(x>9)write(x/10);putchar(x%10+48);
}lint n,A,B,C;
int u[N],v[N],w[N];
ull Rand(ull &k1,ull &k2) {ull k3=k1, k4=k2;k1=k4;k3^=(k3<<23);k2=k3^k4^(k3>>17)^(k4>>26);return k2+k4;
}void GetData() {ull x,y;n=read() ,A=read() ,B=read();C=read() ,x=read() ,y=read();for(int i=1;i<=n;i++) {u[i]=Rand(x,y)%A+1;v[i]=Rand(x,y)%B+1;w[i]=Rand(x,y)%C+1;if(Rand(x,y)%3==0) u[i]=A;if(Rand(x,y)%3==0) v[i]=B;if((u[i]!=A) && (v[i]!=B)) w[i]=C; }
}int xma[N],yma[N];
int xm[N],ym[N];
lint aa,bb;signed main() {GetData();for(int i=1;i<=n;i++) {if(w[i]==C) {xma[v[i]]=max(xma[v[i]],u[i]);yma[u[i]]=max(yma[u[i]],v[i]);}if(v[i]==B) xm[w[i]]=max(xm[w[i]],u[i]);if(u[i]==A) ym[w[i]]=max(ym[w[i]],v[i]);}for(int i=B;i>=1;i--) xma[i]=max(xma[i],xma[i+1]);for(int i=A;i>=1;i--) yma[i]=max(yma[i],yma[i+1]);for(int i=C;i>=1;i--) {xm[i]=max(xm[i],xm[i+1]);ym[i]=max(ym[i],ym[i+1]);}lint S=0,sa=0,sb=0,ans=0,z=1;for(int i=1;i<=A;i++) S+=z*(B-yma[i]);sa=sb=S;aa=A,bb=B;for(int i=1;i<=C;i++) {if(yma[xm[i]+1]<=ym[i]) {ans+=z*(A-xm[i])*(B-ym[i]);}else {while(aa>xm[i]) {sa-=B-yma[aa], aa--;}while(bb>ym[i]) {sb-=A-xma[bb] ,bb--;}ans+=(S-sa-sb);}}ans=z*A*B*C-ans;write(ans);return 0;
}
我是B题
概率期望，狗都不做
Part1
容易发现，如果我们知道哪一个物品是最后留下的，那他最后留下的概率非常好求，只与他前面的数量和后面的数量有关。就是前面的删光，后面的删光，就剩他一个的概率。
Part2
考虑枚举每一个数 \(x\)，计算其概率，设 \(f_{i,j,k}\) 表示到了第 \(i\) 道工序，\(x\) 前剩 \(j\) 个，后面剩 \(k\) 个的概率，由 \(f_{i,j,k}\) 转移到 \(f_{i+1,j-1,k}\) 和 \(f_{i+1,j,k-1}\) ,转移系数只与 \(j\) , \(k\) , \(p_i\) 有关，比较好想。
复杂度 \(\Theta(n^3)\)
好像还可以 \(\Theta(n^2)\) 过。
点击查看代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>#define int long longconst int mod=1e9+7;
const int MAXN=310;using namespace std;inline int read() {int f=1,x=0;char ch=getchar();while(ch>'9' || ch<'0') {if(ch=='-') {f=-1;}ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return f*x;
}inline void write(int x) {cout<<x;putchar('\n');
}int n,ans;
int p[MAXN];
int dp[MAXN][MAXN];
int mi[MAXN][MAXN];void prework() {for(int i=1;i<=n;i++) {mi[i][0]=1;int base=(1-p[i]+mod)%mod;for(int j=1;j<=n;j++) {mi[i][j]=mi[i][j-1]*base%mod;}}
}void init(int x) {for(int i=0;i<=n;i++) {for(int j=0;j<=x;j++) {dp[i][j]=0;}}
}signed main() {n=read();for(int i=1;i<n;i++) {p[i]=read()%mod;}prework();for(int g=1;g<=n;g++) {init(g);dp[0][g-1]=1;for(int i=0;i<n;i++) {for(int j=0;j<g;j++) {dp[i+1][j]=(dp[i+1][j]+dp[i][j]*mi[i+1][j+1]%mod)%mod;if(j>0) {int pp=(1-mi[i+1][j]+mod)%mod;dp[i+1][j-1]=(dp[i+1][j-1]+dp[i][j]*pp%mod)%mod;}}}ans=(ans+g*dp[n-1][0])%mod;}write(ans);return 0;
}
子集
先不考虑 \(F_0\) 的值，先推导公式。
已知：
考虑直接算,有：
那么：
考虑有多少个 \(T\) 包含 \(U\):
考虑组合意义：
继续推导 \(F_3(S)\) 然后：
同样的道理，考虑 \(F_0(U)\) 前面的系数 , 是 \(2\) 的每次枚举的 \(T\) 剩余的大小的次幂:
二项式定理：
根据数学归纳，即可得出结论：
更严谨的证明：
假设有上式成立，那么：
考虑对于每一个和为 \(M\) 的子集 \(T\subseteq S\)的贡献，最后加起来，。
十分显然的 \(dp\) 方程，设 \(f_{i,j,k}\) ,表示考虑到第 \(i\) 个数，已经选了 \(j\) 个，和为 \(k\) 的方案数，答案即为 \(\sum_{i=0}f_{n,i,M}·k^{n-i}\)
方程为：
复杂度为 \(\Theta(n^2M)\) ,可以拿到 \(60\) 分。
考虑优化 ，设 \(g_{i,j}\) 为 $a_1,a_2,a_3 \dots a_i $ 所有的和为 \(j\) 的子集的贡献和；
有状态转移方程：
时间复杂度为 \(\Theta(nM)\)
点击查看代码
#include <iostream>
#include <cstdio>#define int long longconst int mod=1e9+7;
const int MAXN=5010;using namespace std;inline int read() {int f=1,x=0;char ch=getchar();while(ch>'9' || ch<'0') {if(ch=='-') {f=-1;}ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return f*x;
}inline void write(int x) {cout<<x;putchar('\n');
}int T,n,m,k;
int a[MAXN];
int dp[MAXN][MAXN];void solve() {dp[0][0]=1;for(int i=1;i<=n;i++) {for(int j=0;j<=m;j++) {dp[i][j]=dp[i-1][j]*k%mod;if(j>=a[i]) dp[i][j]=(dp[i][j]+dp[i-1][j-a[i]])%mod;}}write(dp[n][m]);
}signed main() {T=read();while(T--) {n=read() ,m=read() ,k=read();for(int i=1;i<=n;i++) {a[i]=read();}solve();}return 0;
}
