湖北2026省选试机题目 - 填充

填充（fill）

题目大意

现在给你无数个边长为 \(1\) 菱形，四个角分别为 \(60 ^ {\circ} , 120 ^ {\circ},60 ^ {\circ},120 ^ {\circ}\)，问有多少个方案，能够密铺边长为 \(n\) 的正六边形，答案对 \(998244353\) 取模。本题多测。

输入格式

第一行一个数 \(T\)，表示数据组数。
接下来的 \(T\) 行，每行一个数字 \(n\) 表示需要密铺的正六边形的边长。

输出格式

共 \(T\) 行，每行一个整数，表示答案对 \(998244353\) 取模后的结果。

样例

样例输入 #1

1
1

样例输出 #1

2

样例输入 #2

2
3
100

样例输出 #2

980
951252372

样例解释 #1

一共有两种铺法，如图：

说明与提示

数据范围

对于 \(10 \%\) 的数据， \(n \le 2\)；
对于另外 \(30 \%\) 的数据，\(n \le 3\)；
对于另外 \(20 \%\) 的数据，\(n \le 10\)；
对于另外 \(20 \%\) 的数据，\(n \le 200\);
对于 \(100 \%\) 的数据，\(n \le 10^6,T \le 5\)。

解法

暂时不写，省选结束之后再研究。欢迎各路 dalao 来研究此题。本蒟蒻在场上坐牢一小时获得的零分的好成绩。

放个标程。

标程

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3000007;
const int mod = 998244353;
const int lim = 3e6;
typedef long long LL;
LL fact[maxn], inv[maxn];
LL fast_pow(LL b, int k) {
    LL s = 1;
    while(k) {
        if(k & 1)
            s = s * b % mod;
        b = b * b % mod;
        k >>= 1;
    }
    return s;
}
int main() {
    freopen("fill.in", "r", stdin);
    freopen("fill.out", "w", stdout);
    for(int i = fact[0] = 1; i <= lim; i++)
        fact[i] = fact[i - 1] * i % mod;
    inv[lim] = fast_pow(fact[lim], mod - 2);
    for(int i = lim; i > 0; i--)
        inv[i - 1] = inv[i] * i % mod;
    int n;
    int T;
    cin >> T;
    while(T--) {
        cin >> n;
        LL ans = 1;
        for(int i = 1; i <= n; i++)
            ans = ans * fact[i + 2 * n - 1] % mod * fact[i - 1] % mod * inv[i + n - 1] % mod * inv[i + n - 1] % mod;
        cout << ans << '\n';
    }
    
    return 0;
}

题解链接

如果侵权，请联系删除。