8.04 接着自闭的杭电5
1001-Tetrahedron
题意
$a$ 、$b$ 、$c$ 为 $[1,n]$ 的随机数,将其分别作为直角三棱锥的三条直角边。设直角顶点为 $P$ ,过 $P$ 的高为 $h$ ,求 $\frac{1}{h^2}$ 的期望值。
思路
对于直角三棱柱有结论 $\frac{1}{h^2}=\frac{1}{a^2}+\frac{1}{b^2}+\frac{1}{c^2}$ ,且 $a$ 、$b$ 、$c$ 是等价的,故可以转化为:求 $[1,n]$ 内随机数 $x$ 的 $E(\frac{3}{x^2})$ 。因为有 $2e6$ 组数据,所以需要预处理。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| #include<bits/stdc++.h> #define pf printf #define sc(x) scanf("%d", &x) #define rep(i,s,e) for(int i=(s); i<(e); ++i) using namespace std; const int maxn = 6e6 + 5; const int mod = 998244353; int qpow(int a,int b){ int ans=1; while(b>0){ if(b&1) ans=1ll*ans*a%mod; b>>=1; a=1ll*a*a%mod; } return ans; } int p[maxn],res[maxn],m[maxn],z[maxn],ans[maxn]; int solve(){ int n; sc(n); return pf("%d\n",ans[n]); } int main(){ res[0]=1; rep(i,1,maxn){ p[i]=1ll*i*i%mod; res[i]=1ll*res[i-1]*p[i]%mod; m[i]=1ll*i*res[i]%mod; m[i]=qpow(m[i],mod-2); z[i]=1ll*z[i-1]*i%mod*i%mod+res[i-1]; if(z[i]>=mod) z[i]-=mod; ans[i]=3ll*z[i]*m[i]%mod; } int _; sc(_); while(_--) solve(); }
|
1003-Boring Game
题意
有 $n$ 张纸,左向右折 $k$ 次。之后从上到下给每层的正背面标号,保证是 $1-2 * n * 2 ^ k$ 的排列。问将纸复原后编号是什么样的。
思路
和小转有仇的 模拟 (虽然是赛时想假了) 。折一次标号就转一次。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| #include<bits/stdc++.h> #define pf printf #define sc(x) scanf("%d", &x) #define mst(a,x) memset(a, x, sizeof(a)) #define rep(i,s,e) for(int i=(s); i<(e); ++i) #define dep(i,e,s) for(int i=(e); i>=(s); --i) using namespace std; const int maxn = 5e5 + 5; int a[maxn]; vector<int>vv[1050]; void solve(){ int n,k; sc(n); sc(k); int t=1<<k,sum=2*n*t; mst(vv,0); rep(i,1,sum+1) sc(a[i]),vv[t].push_back(a[i]); reverse(vv[t].begin(),vv[t].end()); rep(i,0,k) for(int j=t-(1<<i)+1,u=j-1;j<=t;++j,--u){ int s=vv[j].size()/2; rep(l,0,s){ vv[u].push_back(vv[j].back()); vv[j].pop_back(); } } dep(i,2*n-1,0) rep(j,1,t+1) pf("%d%c",vv[j][i]," \n"[!i&&j==t]); } int main(){ int _; sc(_); while(_--) solve(); }
|
1008-Set2
题意
有一个包含 $1-n$ 的 $set$ ,给定 $k$ ,做若干轮删除操作直到 $set$ 里元素个数不多于 $k$ 个。
每次删除操作是先删除一个最小的数,再随机删除 $k$ 个数。
问每个元素留下来的期望是多少。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| #include<bits/stdc++.h> #define pf printf #define sc(x) scanf("%d", &x) #define rep(i,s,e) for(int i=(s); i<(e); ++i) #define dep(i,e,s) for(int i=(e); i>=(s); --i) using namespace std; const int mod = 998244353; int dp[5005]; int qpow(int a,int b){ int ans=1; while(b>0){ if(b&1) ans=1ll*ans*a%mod; b>>=1; a=1ll*a*a%mod; } return ans; } int solve(){ int n,k,r; sc(n); sc(k); r=n%(1+k); rep(i,0,r) dp[i]=1; rep(i,r,n){ dp[i]=0; if((n-i)%(k+1)==1) continue; int inv=qpow(i+1,mod-2); dep(j,i,0){ dp[j]=1ll*dp[j]*(i-j)%mod*inv%mod; if(j) (dp[j]+=1ll*dp[j-1]*j%mod*inv%mod)%=mod; } } dep(i,n-1,0) pf("%d%c",dp[i]," \n"[!i]); } int main(){ int _; sc(_); while(_--) solve(); }
|
1012-Set1
题意
集合有 $1-n$ 的数,其中 $n$ 为奇数。每次操作删除一个最小的数再随机删除一个剩下的数。问每个数剩下的概率。
思路
首先必有 $n/2$ 轮,所以前 $n/2$ 个数留下来的概率必为 $0$ 。设剩下数个数为 $m$ ,则每个数留下来的方案数为 $C^{i-1}_{m-1+i-1}$ ,总方案数为 $2^{m-1+i-1}$ 。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| #include<bits/stdc++.h> #define pf printf #define sc(x) scanf("%d", &x) #define rep(i,s,e) for(int i=(s); i<(e); ++i) #define dep(i,e,s) for(int i=(e); i>=(s); --i) using namespace std; const int maxn = 5e6 + 5; const int mod = 998244353; int qpow(int a,int b){ int ans=1; while(b>0){ if(b&1) ans=1ll*ans*a%mod; b>>=1; a=1ll*a*a%mod; } return ans; } int jc[maxn],inv[maxn],inv2[maxn]; int C(int s,int x){ return 1ll*jc[x]*inv[s]%mod*inv[x-s]%mod; } void solve(){ int n; sc(n); rep(i,1,n/2+1) pf("0 "); n=(n+1)/2; rep(i,1,n+1) pf("%d%c",1ll*C(i-1,n+i-2)*inv2[n+i-2]%mod," \n"[i==n]); } int main(){ jc[0]=inv[0]=inv2[0]=1; int in2=qpow(2,mod-2); rep(i,1,maxn) jc[i]=1ll*jc[i-1]*i%mod,inv2[i]=1ll*inv2[i-1]*in2%mod; inv[maxn-1]=qpow(jc[maxn-1],mod-2); dep(i,maxn-2,1) inv[i]=1ll*inv[i+1]*(i+1)%mod; int _; sc(_); while(_--) solve(); }
|