HDU 多校第五场 Tetrahedron(1001)，Paperfolding（1009）

Tetrahedron：
写这个题时候，我和我的队友三人核对了一下题意后就开始写了，一开始对样例呢么大不敢相信，但是猜测可能是分数的缘故，然后推了一下，用逆元求了下结果确实和样例一模一样，然后有讨论了一下规律，最后我们三人得到规律$E(n)=3(sum(1/1*1+1/2*2+....1/n*n)/n)$E(n)=3(sum(1/1∗1+1/2∗2+....1/n∗n)/n)，但我第一发TLE了，我很奇怪感觉O(N)的时间复杂度应该不会T啊，感觉有可能爆了乘法，我又写了龟速乘，又T了，之后和队友讨论了一下，算了一下时间复杂度，然后预处理了一波就A了，早知道直接测一下最大样例了。

参考代码：

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <math.h>
using namespace std;
typedef long long ll;
//#define ll long long
const ll N = 1e3 + 5;
const ll maxn = 6e6 + 20;
const ll mod = 998244353;
ll inv[maxn], vis[maxn], dis[maxn];
ll fac[maxn], a[maxn], q[maxn];
vector<ll> vec;
//typedef pair<ll, ll> p;
//priority_queue<p, vector<p>, greater<p> > m;
ll max(ll a, ll b) { return a > b ? a : b; }
ll min(ll a, ll b) { return a < b ? a : b; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }
map<ll, ll> mp;
ll ksm(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}
ll dp[maxn];
string p = "abacaba";
void init()
{
    ll ans = 0;
    for (ll i = 1; i <= 6000001; i++)
    {
        ll x = ((i * i) % mod);
        ans = (ans + (ksm(x, mod - 2) % mod));
        dp[i] = (ans * 3) % mod;
    }
}
int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    ll t;
    // ll k = 1;
    init();
    scanf("%lld", &t);
    while (t--)
    {
        ll n;
        scanf("%lld", &n);
        printf("%lld\n", dp[n] * ksm(n, mod - 2) % mod);
    }
}

Paperfolding：
这题也是个求期望的题，我们没找到规律，写了快两个小时，我撕了一垃圾桶的纸，还是没找到，然后就补一下。
下面给出规律和公式推到：

参考代码：

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <math.h>
using namespace std;
typedef long long ll;
//#define ll long long
const ll N = 1e3 + 5;
const ll maxn = 6e6 + 20;
const ll mod = 998244353;
ll inv[maxn], vis[maxn], dis[maxn];
ll fac[maxn], a[maxn], q[maxn];
vector<ll> vec;
//typedef pair<ll, ll> p;
//priority_queue<p, vector<p>, greater<p> > m;
ll max(ll a, ll b) { return a > b ? a : b; }
ll min(ll a, ll b) { return a < b ? a : b; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }
map<ll, ll> mp;
ll ksm(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}
ll dp[maxn];
string p = "abacaba";
void init()
{
    ll ans = 0;
    for (ll i = 1; i <= 6000001; i++)
    {
        ll x = ((i * i) % mod);
        ans = (ans + (ksm(x, mod - 2) % mod));
        dp[i] = (ans * 3) % mod;
    }
}
int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    ll t;
    // ll k = 1;
    //init();
    scanf("%lld", &t);
    while (t--)
    {
        ll n;
        scanf("%lld", &n);
        ll ans = (1ll + ksm(2, n) + (2 * ksm(3, n) % mod) * ksm(ksm(2, mod - 2), n) % mod) % mod;
        printf("%lld\n", ans);
    }
}