2020年杭电多校第五场题解Tetrahedron、Boring Game、Paperfolding

Tetrahedron（数学推导，逆元）

题目传送门

Tetrahedron

思路

公式的推导，显然可以得到

$\frac{1}{h^2}=\frac{1}{a^2} + \frac{1}{b^2} + \frac{1}{c^2}$

对于期望的计算，因为a、b、c是等价的，所以可以直接计算$\frac{1}{a^2}$的期望然后乘以3
而$\frac{1}{a^2}$的期望：

$(\frac{1}{1^2}*\frac{1}{n}+\frac{1}{2^2}*\frac{1}{n}+......+\frac{1}{(n-1)^2}*\frac{1}{n}+\frac{1}{n^2}*\frac{1}{n})$

所以我们可以将$\frac{1}{n}$提出来，可以先对期望打表

AC Code

#include<cstdio>
#include<iostream>
using namespace std;
#define ll long long
// #define TDS_ACM_LOCAL
const int mod=998244353;
const int N=6e6;
ll inv[N+9], a[N+9];
int n;
ll quick_pow(ll a, ll b)
{ 
	ll res = 1;
	while (b)
	{
		if (b & 1)
			res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

void init(){
    inv[1]=a[1]=1;
    for(int i=2; i<=N; i++) inv[i]=(mod - mod/i) *inv[mod%i]%mod;
    for(int i=2; i<=N; i++) a[i]=(a[i-1]+(inv[i]*inv[i])%mod)%mod;
}

void solve(){
    cin>>n;
    cout<<(a[n]*quick_pow(n,mod-2)*3)%mod<<endl;
    return ;
}   

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    init();
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

Boring Game

题目传送门

Boring Game

题目大意

有n张纸，将其连续的从左向右折叠 k 次，然后上到下标号
求将纸重新展开后的序号序列

思路

直接模拟展开的过程即可，采取vector存序号
每次将前一半的序号放到后一半的序号的前面，注意到翻转会使得上一半的序号反过来，所以需要提前翻转一下

AC Code

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
using namespace std;
#define INF 0x3f3f3f3f
// #define TDS_ACM_LOCAL
const int N=5e5 +9;
int n, k, mx, x, mid;
vector<int> z[N];
void solve(){
    cin>>n>>k;
    mx=2*n*pow(2,k);
    for(int i=1; i<=mx; i++)    z[i].clear();
    for(int i=1; i<=mx; i++)   cin>>x, z[i].push_back(x);
    mid=1;
    for(int i=1; i<=k; i++){
        mid=(mid+mx)>>1;                    
        for(int j=mid+1; j<=mx; j++){
            int p=mid-(j-mid-1);                    //上半部分的下标，从中间往上走
            reverse(z[p].begin(), z[p].end());      //提前翻转上半部分对应的值，因为展开后值会反转
            z[j].insert(z[j].begin(), z[p].begin(), z[p].end());    //将上半部分对应的序列插入下半部分相应的位置的前面
            z[p].clear();                           //清空上半部分的翻转的序列
        }
    }
    for(int i=mx-2*n+1; i<=mx; i++){
        for(auto t:z[i])    cout<<(t==z[mx-2*n+1].front() ? "":" ")<<t;             //最后一个数字后面没有空格
    }
    cout<<endl;
    return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

Paperfolding

题目传送门

Paperfolding

题目大意

给你n次操作机会，你可以将一张纸向上下左右任意一方向折叠，总共可折叠n次，求折叠完后十字切割能切出来的纸片的数量

思路

官方题解：

模拟一下可以看出水平对折和垂直对折的答案相对独立
对于$x$次水平对折和$y$垂直对折答案是 $(2^x+1)(2^y+1)$，
这个公式你可以试着模拟一下就会发现左右对折影响的是竖向折痕，每折叠一次$*2$，上下对折同理

因为通过反向逐操作还原，可以看到刀的痕迹的数量变化是每次在某一维倍增的
因此，相当于一张纸，水平和竖直分别切了$2^x, 2^y$刀
所以数学期望为

$\frac{1}{2^n} ∑^n_{i=0}​ C_n^i (2^i +1)(2^{n−i} +1)$

这个公式很容易就可以得出来，但是在这里复杂度仍然很高$O(n×log(n))$，所以还需要化简
可以先将括号打开

$\frac{1}{2^n} ∑^n_{i=0}​[C_n^i (2^n +1)+C_n^i(2^{n−i} +2^i)]$

然后想到二项式定理

$C_n^0+C_n^1+C_n^2+......+C_n^{n-1}+C_n^n$

所以可以得到

$∑^n_{i=0}C_n^i=2^n$

$3^n=(2+1)^n=∑^n_{i=0}C_n^i2^i或者=​∑^n_{i=0}C_n^i2^{n-i}$

根据上面两个公式，我们可以将原来的公式换成

$\frac{1}{2^n}×(2^n×(2^n+1)+2×3^n)$

所以最终的公式就是

$2^n+1+\frac{2×3^n}{2^n}$

AC Code

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
// #define TDS_ACM_LOCAL
const int mod=998244353;
ll quick_pow(ll a, ll b)
{ 
	ll res = 1;
	while (b)
	{
		if (b & 1)
			res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

void solve(){
    ll n;
    cin>>n;
    cout<<((quick_pow(2,n)+1)%mod +((2*quick_pow(3,n))%mod*quick_pow(quick_pow(2,n),mod-2))%mod)%mod<<endl;
    return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

本文地址：https://blog.csdn.net/xmyrzb/article/details/107852974