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 组数据，所以需要预处理。
代码
代码语言：javascript复制#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("%dn",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 的排列。问将纸复原后编号是什么样的。
思路
和小转有仇的 模拟 (虽然是赛时想假了) 。折一次标号就转一次。
代码
代码语言：javascript复制#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 个数。
问每个元素留下来的期望是多少。
代码
代码语言：javascript复制#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} 。
代码
代码语言：javascript复制#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();
}
