1001.Tetrahedron

向量公式法求期望，前缀和

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n;
const int mod=998244353;
const int maxn=6e6+10;
ll ny(ll x)
{
    ll ans=1,n=mod-2;
    while(n)
    {
        if(n%2==1)
            ans*=x,ans%=mod;
        x*=x;
        x%=mod;
        n/=2;
    }
    return ans;
}
ll a[maxn],b[maxn];
int main()
{
    cin>>t;
    a[0]=1;
    for(int i=1;i<=maxn-10;i++)
    {
        a[i]=a[i-1]*i;
        a[i]%=mod;
        a[i]*=i;
        a[i]%=mod;
    }
    b[0]=0;
    for(int i=1;i<=maxn-10;i++)
    {
        b[i]=b[i-1]*i;
        b[i]%=mod;
        b[i]*=i;
        b[i]%=mod;
        b[i]+=a[i-1];
        b[i]%=mod;
    }
    while(t--)
    {
        scanf("%lld",&n);
        ll p=n*a[n];
        p%=mod;
        ll ans=ny(p);
        ans%=mod;
        ans*=3;
        ans*=b[n];
        ans%=mod;
        printf("%lld\n",ans);

    }
    return 0;
}

1009.Paperfolding

模拟

#include <bits/stdc++.h>
using namespace std;

#define LL long long

const LL mod = 998244353;
const LL N = 6e6 + 5;

LL qpow(LL x, LL n)
{
    x %= mod;
    if (x == 1)
        return 1;
    LL ans = 1;
    while (n)
    {
        if (n % 2 == 1)
            ans = (ans * x) % mod;
        x = x * x % mod;
        n /= 2;
    }
    return ans % mod;
}

LL get_inv(LL x) { return qpow(x, mod - 2); }

LL sum[N];

int main()
{
    for (LL i = 1; i < N; i++)
        sum[i] = (sum[i - 1] + get_inv(i * i)) % mod;
    int T;
    scanf("%d", &T);
    while (T--)
    {
        LL n;
        scanf("%lld", &n);
        printf("%lld\n", 3LL * sum[n] % mod * get_inv(n) % mod);
    }
    return 0;
}

1012.Set1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n;
const int mod=998244353;
const int maxn=5e6+10;
ll ny(ll x,ll y)
{
    ll ans=1;
    while(y)
    {
        if(y%2==1)
            ans*=x,ans%=mod;
        x*=x;
        x%=mod;
        y/=2;
    }
    return ans;
}
ll ans,p,s;
ll a[maxn],b[maxn];
map<ll,ll>m,q;
int main()
{
    cin>>t;
    ll s=1;
    for(int i=1;i<=maxn-10;i++)
    {
        s*=i;
        s%=mod;
        a[i]=s;
        //cout<<a[i]<<endl;
    }
    b[3]=2;
    int x=4;
    for(int i=5;i<=maxn-10;i+=2)
    {
        b[i]=b[i-2]*x;
        b[i]%=mod;
        x+=2;
        x%=mod;
        //cout<<b[i]<<" ";
    }
    while(t--)
    {
        cin>>n;
        if(n==1)
        {
            cout<<1<<endl;
            continue;
        }
        for(int i=1;i<=n/2;i++)
        cout<<"0 ";
        //cout<<b[n]<<endl;
        ll k=ny(b[n],mod-2);
        //cout<<a[n/2]<<endl;
        ans=a[n/2]*k;
        ans%=mod;
        cout<<ans<<" ";
        ll u=2;
        for(int i=n/2+2;i<n;i++)
        {
            //cout<<i-1<<endl;
            ans*=((i-1)*ny(u,mod-2))%mod;
            ans%=mod;
            u+=2;
            u%=mod;
            cout<<ans<<" ";
        }
        cout<<ans<<endl;
    }
    return 0;
}