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

发布于 2020-08-06  0 次阅读


Tetrahedron(数学推导,逆元)

思路:

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次,求折叠完后十字切割能切出来的纸片的数量

思路:

官方题解:

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

Set1

题目大意:

给你一个n(保证n为奇数),在{1,2,…,n}的集合S中,每次删除当前集合中最小的元素,再随机删掉1个元素
每个元素最后被留下来的概率

思路:

推公式没什么好说的,看官方题解吧

在这里插入图片描述

AC Code:

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
// #define TDS_ACM_LOCAL
const int N=5e6 +9;
const ll mod=998244353;
int n;
ll ans;
ll jc[N], inv[N], a[N], invs[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(){
	jc[0]=jc[1]=1;
	inv[0]=inv[1]=1;
	invs[0]=invs[1]=1;
	for(int i=2; i<N; i++){
		jc[i]=jc[i-1]*i%mod;
		invs[i]=(mod-mod/i)*invs[mod%i]%mod;
		inv[i]=inv[i-1]*invs[i]%mod;
	}
	return ;
}
void solve(){
	ans=0;
	cin>>n;
	if(n==1)	{cout<<"1"<<endl; return ;}
	cout<<"0";
	for(int i=2; i<=n; i++){
		if(i<=n/2)	{cout<<" "<<"0"; continue;}
		a[i]=((jc[i-1]*quick_pow(inv[2], (2*i-n-1)/2)) %mod *inv[(2*i-n-1)/2]) %mod;
		ans=(ans+a[i])%mod;
	}
	ans=quick_pow(ans, mod-2);
	for(int i=n/2+1; i<=n; i++)	cout<<" "<<a[i]*ans%mod;
	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
	init();
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

平平无奇的大学在读本科生