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

题目传送门

题目大意

有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

题目传送门

题目大意

给你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

您可能感兴趣的文章:

如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！

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

2020年08月10日 | 移动技术网IT编程 | 我要评论

Tetrahedron（数学推导，逆元）

题目传送门

思路

$\frac{1}{h^2}=\frac{1}{a^2} + \frac{1}{b^2} + \frac{1}{c^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})$

AC Code

Boring Game

题目传送门

题目大意

思路

AC Code

Paperfolding

题目传送门

题目大意

思路

官方题解：

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

$\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

您可能感兴趣的文章:

相关文章:

网友评论


验证码：

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

2020年08月10日 | 移动技术网IT编程 | 我要评论

Tetrahedron（数学推导，逆元）

题目传送门

思路

1h2=1a2+1b2+1c2\frac{1}{h^2}=\frac{1}{a^2} + \frac{1}{b^2} + \frac{1}{c^2}h21​=a21​+b21​+c21​

(112∗1n+122∗1n+......+1(n−1)2∗1n+1n2∗1n)(\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})(121​∗n1​+221​∗n1​+......+(n−1)21​∗n1​+n21​∗n1​)

AC Code

Boring Game

题目传送门

题目大意

思路

AC Code

Paperfolding

题目传送门

题目大意

思路

官方题解：

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

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

Cn0+Cn1+Cn2+......+Cnn−1+CnnC_n^0+C_n^1+C_n^2+......+C_n^{n-1}+C_n^nCn0​+Cn1​+Cn2​+......+Cnn−1​+Cnn​

∑i=0nCni=2n∑^n_{i=0}C_n^i=2^n∑i=0n​Cni​=2n

3n=(2+1)n=∑i=0nCni2i或者=​∑i=0nCni2n−i3^n=(2+1)^n=∑^n_{i=0}C_n^i2^i或者=​∑^n_{i=0}C_n^i2^{n-i}3n=(2+1)n=∑i=0n​Cni​2i或者=​∑i=0n​Cni​2n−i

12n×(2n×(2n+1)+2×3n)\frac{1}{2^n}×(2^n×(2^n+1)+2×3^n)2n1​×(2n×(2n+1)+2×3n)

2n+1+2×3n2n2^n+1+\frac{2×3^n}{2^n}2n+1+2n2×3n​

AC Code

您可能感兴趣的文章:

相关文章:

网友评论

$\frac{1}{h^2}=\frac{1}{a^2} + \frac{1}{b^2} + \frac{1}{c^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}{2^n} ∑^n_{i=0} C_n^i (2^i +1)(2^{n−i} +1)$

$\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}$