保龄力！！！！
我是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 __int128
using 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 long
const 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\) 的值，先推导公式。
已知：
\[F_k=\sum_{T \subseteq S} F_{k-1}(T) \]考虑直接算,有：
\[F_1(S)= \sum_{T \subseteq S }F_0(T) \]那么：
\[F_2(S)=\sum_{T \subseteq S} F_1(T) \]\[F_2(S)=\sum_{T \subseteq S} \sum_{U \subseteq T} F_0(U) \]考虑有多少个 \(T\) 包含 \(U\):
\[F_2(S)=\sum_{U \subseteq S} F_0(U) \sum_{i=0} ^ { |S|-|U| } \dbinom{|S|-|U|}{i} \]考虑组合意义：
\[F_2(S)=\sum_{U \subseteq S} F_0(U) · 2^{|S|-|U|} \]继续推导 \(F_3(S)\) 然后：
\[F_3(S)=\sum_{T \subseteq S} F_2(T) \]\[F_3(S)=\sum_{T \subseteq S} \sum_{U \subseteq S} F_0(U) · 2^{ |T|-|U|} \]同样的道理，考虑 \(F_0(U)\) 前面的系数 , 是 \(2\) 的每次枚举的 \(T\) 剩余的大小的次幂:
\[F_3(S)=\sum_{U \subseteq S} F_0(U) · \sum_{i=0}^{|S|-|U|} \dbinom{|S|-|U|}{i}·2^i \]二项式定理：
\[F_3(S)=\sum_{U \subseteq S} F_0(U) ·3^{|S|-|U|} \]根据数学归纳，即可得出结论：
\[F_k(S)=\sum_{T \subseteq S} F_0(T) ·k^{|S| -|T|} \]更严谨的证明：
假设有上式成立，那么：
\[F_{k+1}(S)=\sum_{T \subseteq S} F_k(T) \]\[=\sum_{T \subseteq S}\sum_{U \subseteq T} F_0(U) ·k^{|S| -|T|} \]\[=\sum_{U \subseteq S} \]考虑对于每一个和为 \(M\) 的子集 \(T\subseteq S\)的贡献，最后加起来，。
十分显然的 \(dp\) 方程，设 \(f_{i,j,k}\) ,表示考虑到第 \(i\) 个数，已经选了 \(j\) 个，和为 \(k\) 的方案数，答案即为 \(\sum_{i=0}f_{n,i,M}·k^{n-i}\)
方程为：
\[f_{i,j,k}=f_{i-1,j,k}+f_{i-1,j-1,k-a_i} \]复杂度为 \(\Theta(n^2M)\) ,可以拿到 \(60\) 分。
考虑优化 ，设 \(g_{i,j}\) 为 $a_1,a_2,a_3 \dots a_i $ 所有的和为 \(j\) 的子集的贡献和；
有状态转移方程：
\[g_{i,j}=g_{i-1,j}*k+g_{i-1,j-a_i} \]时间复杂度为 \(\Theta(nM)\)
点击查看代码
#include <iostream>
#include <cstdio>
#define int long long
const 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;
}