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();
}
|
