填充（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\)。
解法
暂时不写，省选结束之后再研究。
放个标程。
标程
#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;
}
题解链接
如果侵权，请联系删除。