杭电多校第五场补题

1001 Tetrahedron

题目连接：杭电多校第五场1001Tetrahedron
知识点1.逆元的求法
费马小定理：假如a，p互质（ 即gcd(a，p)=1 )，且p是质数，a任意，那 么a^(p-1) %p=1。 也就是说如果m是质数，(bx)%m=1就可以转化成
b*（b^ (m-2) ）%m=1也就是说x=b^(n-2)(mod m)
a^-1=a ^(p-2)

E(n)=3(sum(1/11+1/22+…1/n*n)/n)

//E(n)=3(sum(1/1*1+1/2*2+....1/n*n)/n)
#include<stdio.h>
#include<iostream>
#include<math.h>
#include<string.h>
#include <algorithm>
#include <numeric>
#include <vector> 
#include <functional>
#include <list>
#include <ctype.h>
#include<map>
#include <set>
#define N 6000005
#define M 100
#define ll long long 
#define mod 998244353
using namespace std;
ll a[N];
ll quick(ll a,ll b){
	ll ans=1;
	for(;b;b>>=1){
		if(b&1) ans=ans*a%mod;
		a=(a*a)%mod;
	}
	return ans;
}
int main(){
	ll t;
	for(ll i=1;i<=N;i++){//求逆元的平方，并用前缀和储存数据 
		ll x=(i*i)%mod;
		a[i]=quick(x,mod-2)*3%mod;
		a[i]=(a[i]+a[i-1])%mod；	
	}
	scanf("%lld",&t);
	while(t--){
		ll n;
		scanf("%lld",&n);
		printf("%lld\n",a[n]*quick(n,mod-2)%mod); //根据公式期望是在前缀和的基础上还要/n 
	}
}

1009 Paper folding
题目链接：杭电多校第五场1009Paper folding
若只水平方向或竖直方向折叠可以得出每折一次纸被分割出的数量翻倍，也就是折n次纸的数量即为2^n张。再加上水平竖直切割得 （2 ^n +1）*(2 ^0+1)张。
设水平折x，次竖直折y次，结果为 (2 ^x+1) * （2^y+1）

可以看出跟上一题的解法思路基本一致，只是期望的表达式不同而已。

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<string.h>
#include <algorithm>
#include <numeric>
#include <vector> 
#include <functional>
#include <list>
#include <ctype.h>
#include<map>
#include <set>
#define N 6000005
#define M 100
#define ll long long 
#define mod 998244353
using namespace std;
ll a[N];
ll quick(ll a,ll b){
	ll ans=1;
	for(;b;b>>=1){
		if(b&1) ans=ans*a%mod;
		a=(a*a)%mod;
	}
	return ans;
}

int main(){
	ll t;
	scanf("%lld",&t);
	while(t--){
		ll n;
		scanf("%lld",&n);
		 ll m=(1ll+quick(2,n)+(2*quick(3,n)%mod)*quick(quick(2,mod-2),n)%mod)%mod;
		printf("%lld\n",m); 
	}
}