Press "Enter" to skip to content

2020杭电暑期多校第五场

1001.Tetrahedron

题目链接

题意

已知直角四面体的四条边长度$a,b,c\in [1,n]$,求高$h$的$\frac{1}{h^2}$期望

解题思路

先说结论
$\frac{1}{h^2}=\frac{1}{a^2}+\frac{1}{b^2}+\frac{1}{c^2}$
所以期望为$\frac{3}{n}\sum_{i=1}^{n}\frac{1}{i^2}$,因为T为$2\times10^6$所以我们需要用$O(n)$先预处理出$\frac{1}{n}$和$\sum_{i=1}^{n}\frac{1}{i^2}$的逆元

$$
\begin{align}
&做CE的延长线交AB于K\\
&连接KD\\
&因为 \angle CDB=90^\circ\ \angle CDA=90^\circ\\
&所以 CD\perp DB\ CD\perp AD\\
&所以 CD\perp 平面ADB\\
&所以CD\perp KD\\
&所以\angle CDK=90^\circ\\
&|AB|=\sqrt{a^2+b^2}\\
&|AB|\cdot |KD|=a\cdot b\\
&|KD|=\frac{ab}{\sqrt{a^2+b^2}}\\
&|KD|\cdot|DC|=h\cdot|KC|\\
&|KC|=\sqrt{|KD|^2+c^2}\\
&h=\frac{|KD|\cdot|DC|}{|KC|}\\
&\frac{1}{h^2}=\frac{\frac{a^2b^2}{a^2+b^2}+c^2}{\frac{a^2b^2c^2}{a^2+b^2}}\\&=\frac{a^2b^2+a^2c^2+b^2c^2}{a^2b^2c^2}\\&=\frac{1}{a^2}+\frac{1}{b^2}+\frac{1}{c^2}
\end{align}
$$

参考代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MAXN=(int)6e6+5;
const ll MOD=998244353;
ll _inv[MAXN];
ll inv[MAXN];
void pre(){  
    _inv[0]=_inv[1]=1;  
    for(int i=2;i<MAXN;i++)
        _inv[i]=((MOD-MOD/i)*_inv[MOD%i])%MOD;  
    inv[0]=inv[1]=1;  
    for(int i=2;i<MAXN;i++)
        inv[i]=(_inv[i]*_inv[i])%MOD;
    for(int i=2;i<MAXN;i++)
    inv[i]=(inv[i]+inv[i-1])%MOD;
}    
int main()
{
 
    pre();
    int T,n;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d",&n);
        ll ans=3*inv[n]%MOD;
        ans=ans*_inv[n]%MOD;
        printf("%lld\n",ans);
    }
    return 0;
}

1012.Set1

题目链接

题意

先空着吧

解题思路

方法一:打表找规律

我们先用DFS做一个爆搜的程序,然后找规律

  1. 我们先找分母,也就是总方案数的规律
nQ
32=2
584=2×4
748=2×4×6
9384=2×4×6×8
113840=2×4×6×8×10
1346080=2×4×6×8×10×12
1564512=2×4×6×8×10×12×14
1710321920=2×4×6×8×10×12×14×16

所以我们得到分母为$\lfloor\frac{n}{2}\rfloor!\times2^{\lfloor\frac{n}{2}\rfloor}$
接下来观察观察分子,都从中间项开始,因为易得前$\lfloor\frac{n}{2}\rfloor$均为0

所以我们可以发现规律
以$n=11$时为例$120=\frac{5!}{1!}$$360=\frac{6!}{3!}\times3$$630=\frac{7!}{5!}\times3\times5$$840=\frac{8!}{7!}\times3\times5\times7$$945=\frac{8!}{7!}\times3\times5\times7\times9$

参考代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MAXN=1e7+5;
const ll MOD= 998244353;
ll fra[MAXN];
ll inv[MAXN];
ll powmod(ll a,ll b) {ll res=1;a%=MOD; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}
void pre()
{
    fra[0]=1;
    for(ll i=1;i<MAXN;i++)fra[i]=(fra[i-1]*i)%MOD;
    inv[0]=inv[1]=1;  
    for(ll i=2;i<MAXN;i++)inv[i]=((MOD-MOD/i)*inv[MOD%i])%MOD;
    for(ll i=2;i<MAXN;i++)inv[i]=(inv[i]*inv[i-1])%MOD;
}
int main()
{
    pre();
    int n,T;
    ll ans;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d",&n);
        if(n==1){printf("1\n");continue;}
        int k=n/2;
        for (int i = 1; i <= k; i++)printf("0 ");
        ll tmp=1,ans;
        ll m=inv[k]*powmod(inv[2],k)%MOD;
        for (int i = 0; i < k; i++)
        {
            
            tmp=tmp*(i*2+1)%MOD;
            ans=fra[k+i]*inv[i*2+1]%MOD*tmp%MOD;
            ans=ans*m%MOD;
            printf("%lld ",ans);
        }
        printf("%lld\n",ans);
        
    }
    
    return 0;
}

Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments
0
喜欢聆听每一种不同的观点,欢迎评论。x
()
x