最优解奖获得者:
C y_kx_b
D syf000
为了大家的观赏体验,我们将最优解者的代码放在了解析下方以供大家参考。
A.良串(GOODSTRING)
考虑 $abc$ 和 $cba$ 可能出现的情况只有两种:
- $abcba$ 这种情况只需要删除一个
- $abccba$ 这种情况需要删除两个
如果多个串相连如 $abcbabc$ 怎么办呢?
考虑字符 $b$ 的位置,$b$ 一定在串的中心,因此如果两个 $b$ 相距 $1$ 个字符且串相连,只考虑删除 $1$ 个,每次找到一个字符串匹配便更新标记,只有满足条件的串距离大于 $1$,才有正确的答案,于是我们发现,这种讨论恰好把以上两种可能全部涉及了,因此答案是正确的。
时间复杂度 $O(n)$ 。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
char s[N];
int main()
{
scanf("%s", s + 1);
int n = strlen(s + 1), last = 0, ans = 0;
for (int i = 2; i < n; i ++ )
if (s[i] == 'b' && (s[i - 1] == 'a' && s[i + 1] == 'c' || s[i - 1] == 'c' && s[i + 1] == 'a'))
if (!last || last + 2 < i) ans ++ , last = i;
printf("%d", ans);
return 0;
}
B.良集(GOODSET)
首先对数据范围进行分析,发现元素至多 $2 \times 10^6$ 种,因此产生的集合大小肯定不会超过 $2 \times 10^6$,这个模数可以直接去掉。
对于一个元素 $x$ 在 $A,B$ 集合的出现次数进行判断即可:
-
如果为 $0$ 次,这个元素必不被选择;
-
如果为 $1$ 次,这个元素可以被选择;
-
如果为 $2$ 次,这个元素必须被选择。
因此只需讨论这个元素是否出现过至少一次即可,我们只需要在这个元素初次出现时加一,再次出现时减一即可,最终答案为出现了 $1$ 次的元素数量加一。
时间复杂度 $O(n)$ 。
#include<bits/stdc++.h>
using namespace std;
int n, m, ans;
unordered_map<int, bool> mp;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n + m; i ++ )
{
int a;
scanf("%d", &a);
if (!mp[a]) mp[a] = true, ans ++ ;
else ans -- ;
}
printf("%d", ans + 1);
return 0;
}
【最优解】340ms
from Idontwannabethe
手写哈希的狠人。
#include <bits/stdc++.h>
#define gc getchar_unlocked
using namespace std;
int read() {
int x = 0; char ch = gc();
while(ch > '9' || ch < '0') ch = gc();
while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ 48), ch = gc();
return x;
}
const int N = 1e6 + 10;
namespace HASH {
int head[N], to[N], ne[N], idx1 = 0;
int hsh(int x) {return x % N;}
void insert(int x) {
int p = hsh(x);
to[idx1] = x, ne[idx1] = head[p], head[p] = idx1++;
}
bool query(int x) {
int p = hsh(x);
for(int i = head[p]; ~i; i = ne[i]) if(to[i] == x) return 1;
return 0;
}
}
int main() {
memset(HASH::head, -1, sizeof (int) * N);
int n = read(), m = read(), ans = n + m + 1;
for(int i = 1; i <= n; i++) HASH::insert(read());
for(int i = 1; i <= m; i++) if(HASH::query(read())) ans -= 2;
printf("%d\n", ans);
return 0;
}
C.良界(GOODBORDER)
贪心的想,一个串以 $1$ 开头并且越长越大,因此将序列划分为尽量多的部分最,一个最大 $01$ 串独占一个大区间,剩余的区间全部长度为 $1$,这样得到的和一定是最大的,考虑如何求出最大,类似一个 DP 问题,我们划定一个字符串大小,每次移动一位用memcpy
转移,存储最大字符串,在统计答案时求值即可。
时间复杂度 $O(n\times memcpy)$,由于memcpy
的操作是前移动一位,所以实际复杂度远远小于 $n^2$,根据实际测试估算在 $O(n \log n)$ 左右。
ps:切记不要换成数字来做,否则转移会出大问题!
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, mod = 998244353;
int n, k, maxn, cnt;
char str[N], res[N], ans[N];
int main()
{
scanf("%d%d", &n, &k);
scanf("%s", str);
int len1 = strlen(str), len2 = n - k + 1;
memcpy(res, str, len2);
memcpy(ans, res, len2);
for (int i = 0; i < len1; i ++ )
cnt += (str[i] == '1');
for (int i = n - k + 1; i < len1; i ++ )
{
memcpy(res, res + 1, len2 - 1);
res[len2 - 1] = str[i];
if (strcmp(ans, res) < 0) memcpy(ans, res, len2);
}
for (int i = 0; i < len2; i ++ )
{
cnt -= (ans[i] == '1');
maxn = ((maxn << 1) + (ans[i] == '1')) % mod;
}
cout << maxn + cnt;
return 0;
}
【最优解】205ms
from y_kx_b
后缀数组优化(tql)
#include<bits/stdc++.h>
#define gc getchar
using namespace std;
const int N=114514;
char s[N];
int k;
namespace sort
{
int d[N],d2[N],n;
int cnt[N];
void sort(int key1[],int key2[], int t)
{
memset(cnt,0,sizeof /*cnt*/(int) * (t + 1));
for(int i=0;i<n;i++)
cnt[key2[i]]++;
for(int i=1;i/*<N*/<=t;i++)
cnt[i]+=cnt[i-1];
for(int i=n-1;i>=0;i--)
d[--cnt[key2[i]]]=i;
memset(cnt,0,sizeof (int) * (t + 1));
for(int i=0;i<n;i++)
cnt[key1[i]]++;
for(int i=1;i<= t;i++)
cnt[i]+=cnt[i-1];
for(int i=n-1;i>=0;i--)
d2[--cnt[key1[d[i]]]]=d[i];// not d2[--cnt[key1[i]]]=d[i] !
}
}using namespace sort;
namespace sa
{
#define sa1 sort::d
#define sa2 sort::d2
int key1[N],key2[N],rnk1[N],rnk2[N];
#define len n
void get()
{
for(int i=0;i<len;i++)
rnk1[i] = s[i] == '1' ? 2 : 1;
int t = 2;
for(int l=1;l<=/*len*/k;l<<=1)
{
for(int i=0;i<len;i++)
if(i+l>=len)
key1[i]=rnk1[i],key2[i]=0;
else
key1[i]=rnk1[i],key2[i]=rnk1[i+l];
sort::sort(key1,key2, t);
t=1;rnk2[sa2[0]]=t;
for(int i=1;i<len;i++)
{
if(key1[sa2[i]]==key1[sa2[i-1]]&&key2[sa2[i]]==key2[sa2[i-1]])
rnk2[sa2[i]]=t;
else
rnk2[sa2[i]]=++t;
}
memcpy(rnk1, rnk2, sizeof(int) * len);
if(t==len)break;
}
}
}using namespace sa;
const int mod = 998244353;
int main()
{
scanf("%d%d", &n, &k); k = n - (k - 1);
scanf("%s",s);// cerr << k << " " << s;
get();
long long ans = 0; int LLL = (n - 1) - k + 1;
for(int i = n - 1; ~i; i--) if(sa2[i] <= LLL) {
int j = sa2[i], ans2 = 0;
for(int jj = 0; jj < j; jj++) ans2 += s[jj] == '1';
for(int u = 0; k--; u++, j++) {
ans = ans << 1 | (s[j] == '1');
if(u & 32) u = 0, ans %= mod;
}
for(; j < n; j++) ans2 += s[j] == '1';
ans = (ans + ans2) % mod;
return printf("%lld\n", ans), 0;
}
return 0;
}
D.良数(GOODNUMBER)
离线求区间 $Mex$,我们可以使用莫队算法,每次指针扫过出现次数为 $1$ 的数便加入小根堆,处理询问时判断小根堆堆顶是否符合条件,不符合弹出寻找下一个,直到堆空为止。
时间复杂度 $O(n \log n + q\sqrt{n}\log n)$,实际复杂度可以忽略 $\log n$ 。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int w[N], t[N];
int st[N], ans[N];
vector<int> alls;
priority_queue<int, vector<int>, greater<int>> heap;
struct Node
{
int l, r, id;
}a[N];
bool cmp(Node x, Node y)
{
if (x.l == y.l)
{
if (x.r == y.r) return x.id < y.id;
return x.r < y.r;
}
return x.l < y.l;
}
int find(int x)
{
int l = 0, r = alls.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &w[i]);
alls.push_back(w[i]);
}
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
for (int i = 1; i <= n; i ++ ) t[i] = find(w[i]);
for (int i = 1; i <= m; i ++ )
{
int l, r;
scanf("%d%d", &l, &r);
a[i] = {l, r, i};
}
sort(a + 1, a + m + 1, cmp);
int p = 1, q = 0;
for (int i = 1; i <= m; i ++ )
{
while (q < a[i].r)
{
q ++ ;
if ( ++ st[t[q]] == 1) heap.push(t[q]);
}
while (q > a[i].r)
{
if ( -- st[t[q]] == 1) heap.push(t[q]);
q -- ;
}
while (p < a[i].l)
{
if ( -- st[t[p]] == 1) heap.push(t[p]);
p ++ ;
}
int res = 0;
while (!res && heap.size())
{
int top = heap.top();
if (st[top] != 1) heap.pop();
else res = top;
}
ans[a[i].id] = res;
}
for (int i = 1; i <= m; i ++ )
if (ans[i]) printf("%d\n", alls[ans[i] - 1]);
else puts("0");
return 0;
}
【最优解】
from syf000 872ms
不使用堆,这样免去了排序的复杂度。
#include<bits/stdc++.h>
const int N=1e5+5;
using namespace std;
struct sss{int l,r,id;}q[N];
set<int>s;
int n,m,a[N],kuai,nowl,nowr,ll,rr,ans[N],li[N],cnt[N];
int cmp(sss x,sss y){if(x.l/kuai!=y.l/kuai)return x.l<y.l;return (x.l/kuai)&1?x.r<y.r:x.r>y.r;}
void add(int x){cnt[x]++;if(cnt[x]==1)s.insert(x);else{if(s.find(x)!=s.end())s.erase(s.find(x));}}
void del(int x){cnt[x]--;if(cnt[x]==1)s.insert(x);else{if(s.find(x)!=s.end())s.erase(s.find(x));}}
signed main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;kuai=sqrt(n);
for(int i=1;i<=n;i++)cin>>a[i],li[i]=a[i];
sort(li+1,li+n+1);int len=unique(li+1,li+n+1)-li-1;
for(int i=1;i<=n;i++)a[i]=lower_bound(li+1,li+len+1,a[i])-li;
for(int i=1;i<=m;i++){cin>>q[i].l>>q[i].r;q[i].id=i;}
sort(q+1,q+m+1,cmp);
nowl=1;
for(int i=1;i<=m;i++)
{
ll=q[i].l;rr=q[i].r;
while(nowl>ll)add(a[--nowl]);
while(nowr<rr)add(a[++nowr]);
while(nowl<ll)del(a[nowl++]);
while(nowr>rr)del(a[nowr--]);
if(s.size()!=0)
ans[q[i].id]=li[*s.begin()];
}
for(int i=1;i<=m;i++)
cout<<ans[i]<<'\n';
}
E.良组(GOODGROUP)
考虑如何给一个组的学生同时加分,我们将这些学生按照组别写一个结构体排序,这样就可以映射到一个连续区间,记录下区间的左右即可,同样,给每个学生新的位置都一个指针方便我们单点修改,接下来进行区间询问,询问每个组别的积分总和是否大于阈值,是则对答案贡献 $1$,然后是单点查询值是否大于阈值,使用线段树进行维护即可。
时间复杂度 $O(qm\log n)$ 。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
typedef long long ll;
int n, m, T;
int to[N];
int sum[N], pre[N];
int groupl[N], groupr[N], cnt;
vector<int> v;
struct Student
{
int id, is;
}student[N];
struct Node
{
int l, r;
ll sum, add;
}tr[N << 2];
bool cmp(Student x, Student y)
{
if (x.is == y.is) return x.id < y.id;
return x.is < y.is;
}
void pushup(int u)
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void pushdown(int u)
{
Node &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
if (root.add)
{
left.sum += (ll)(left.r - left.l + 1) * root.add;
right.sum += (ll)(right.r - right.l + 1) * root.add;
left.add += root.add, right.add += root.add;
root.add = 0;
}
}
void build(int u, int l, int r)
{
tr[u] = {l, r};
if (l != r)
{
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int l, int r, int d)
{
if (tr[u].l >= l && tr[u].r <= r)
{
tr[u].sum += (ll)(tr[u].r - tr[u].l + 1) * d;
tr[u].add += d;
}
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, d);
if (r > mid) modify(u << 1 | 1, l, r, d);
pushup(u);
}
}
ll query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
ll res = 0;
if (l <= mid) res = query(u << 1, l, r);
if (r > mid) res += query(u << 1 | 1, l, r);
return res;
}
int main()
{
scanf("%d%d%d", &n, &m, &T);
for (int i = 1; i <= n; i ++ )
{
int a;
scanf("%d", &a);
student[i] = {i, a};
sum[a] ++ ;
}
sort(student + 1, student + n + 1, cmp);
int last = 0;
for (int i = 1; i <= n; i ++ )
{
to[student[i].id] = i;
sum[i] += sum[i - 1];
if (sum[i] != sum[i - 1])
{
pre[i] = last + 1;
last = sum[i];
groupl[i] = pre[i];
groupr[i] = sum[i];
}
else pre[i] = pre[i - 1];
}
build(1, 1, n);
while (T -- )
{
int op;
scanf("%d", &op);
if (op == 1)
{
int x, y;
scanf("%d%d", &x, &y);
if (groupl[x]) modify(1, groupl[x], groupr[x], y);
}
else if (op == 2)
{
int x, y;
scanf("%d%d", &x, &y);
modify(1, to[x], to[x], y);
}
else if (op == 3)
{
ll x, ans = 0;
scanf("%lld", &x);
for (int i = 1; i <= m; i ++ )
{
if (!groupl[i]) continue;
if (query(1, groupl[i], groupr[i]) >= x)
ans ++ ;
}
printf("%lld\n", ans);
}
else
{
int x;
ll y;
scanf("%d%lld", &x, &y);
if (query(1, to[x], to[x]) >= y) puts("Yes");
else puts("No");
}
}
return 0;
}
【最优解】144ms
from Idontwannabethe
#include <bits/stdc++.h>
#define gc getchar_unlocked
using namespace std;
typedef long long ll;
ll read() {
int x = 0; char ch = gc();
while(ch > '9' || ch < '0') ch = gc();
while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ 48), ch = gc();
return x;
}
const int N = 1e5 + 10, M = 200 + 10;
struct block {
int siz;
ll sum, tag;
}T[M];
int belong[N];
ll sc[N];
int main() {
int n = read(), m = read(), q = read();
for(int i = 1; i <= n; i++) T[belong[i] = read()].siz++;
while(q--) {
int op = read(); ll x = read(), y;
switch(op) {
case 1: y = read(), T[x].tag += y, T[x].sum += y * T[x].siz; /*T[x].sum = min(T[x].sum, ll(1e9));*/ break;
case 2: y = read(), sc[x] += y, T[belong[x]].sum += y; break;
case 3: {
int ans = 0;
for(int i = 1; i <= m; i++) ans += T[i].sum >= x;
printf("%d\n", ans);
break;
}
case 4: y = read(), puts(T[belong[x]].tag + sc[x] >= y ? "Yes" : "No"); break;
}
}
return 0;
}
同样此题亦可以使用平衡树(板子题,什么?我还没学,那没事了)
F.良图(GOODGRAPH)
由于给出的图是一张有向图,因此我们可以反向建图利用拓扑求出一个点必须经过的图腾是哪些,使用 bitset
进行转移。
每次询问答案时将两个点的答案取并,并且将每一个点的答案取最小值,答案只可能是并或者最小值的两倍之中的一个,取 $Min$
即可。
时间复杂度 $O(\frac{n+q}{w})$ 。
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int n, m, T;
int h[N], e[N], ne[N], idx;
int w[N], q[N];
bitset<1005> bit[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d%d%d", &n, &m, &T);
for (int i = 2; i <= n; i ++ )
{
int a;
scanf("%d", &a);
add(a, i);
}
for (int i = 1; i <= n; i ++ )
{
int a;
scanf("%d", &a);
w[i] = a - 1;
}
int hh = 0, tt = 1;
q[0] = 1, bit[1][w[1]] = 1;
while (hh <= tt)
{
int ver = q[hh ++ ];
for (int i = h[ver]; ~i; i = ne[i])
{
int j = e[i];
bit[j] = bit[ver];
bit[j][w[j]] = 1;
q[ ++ tt] = j;
}
}
while (T -- )
{
int a, b, cnt = 1000;
scanf("%d%d", &a, &b);
bitset<1005> ans;
cnt = min(cnt, (int)bit[a].count());
ans |= bit[a];
cnt = min(cnt, (int)bit[b].count());
ans |= bit[b];
int p = ans.count();
int Ans = min(p - (p & 1), cnt << 1);
printf("%d\n", Ans);
}
return 0;
}
G.良弹(GOODBOUNCE)
首先给出一个结论,当树的直径为偶数长度且起始点位于中心时,$Bob$ 胜,否则 $Alice$ 胜,我们给出证明。
-
当棋子不位于直径上时,一方如果能够跳到直径中心,那么无论另一方如何移动,只需要将棋子移动到关于中心对称的点上即可,由于操作是对称性的,先手必胜。
-
当树的直径为奇数长度时,树的中心有两个,只要一方跳到其中一个中心上,另一方不可能再跳到树的中心,因此与上一种情况同理
-
当树的直径为偶数长度时,先手若不在中心,则可以跳到中心,先手必胜,先手若在中心,后手一定可以跳到先手跳到任意处的对称点,因此后手必胜。
综上,我们只需要求出树的直径,并判断中点位置即可,当且仅当直径长度为偶数且起始点在树的中心时先手必败,否则先手必胜。
时间复杂度 $O(n)$ 。
ps:这个博弈论怎么没人写啊呜呜~
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, inf = 1e9;
int n, q;
int h[N], e[N << 1], ne[N << 1], idx;
int d1[N], d2[N], p[N], up[N];
bool fail[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
int dfs_u(int u, int f)
{
d1[u] = d2[u] = -inf;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == f) continue;
int d = dfs_u(j, u) + 1;
if (d1[u] <= d)
{
d2[u] = d1[u];
d1[u] = d, p[u] = j;
}
else if (d2[u] < d) d2[u] = d;
}
if (d1[u] == -inf) d1[u] = d2[u] = 0;
return d1[u];
}
void dfs_d(int u, int f)
{
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == f) continue;
if (p[u] == j) up[j] = max(up[u], d2[u]) + 1;
else up[j] = max(up[u], d1[u]) + 1;
dfs_d(j, u);
}
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d%d", &n, &q);
for (int i = 1; i < n; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
dfs_u(1, 0);
dfs_d(1, 0);
int res = inf, d = 0;
for (int i = 1; i <= n; i ++ )
{
res = min(res, max(up[i], d1[i]));
d = max(d, up[i] + d1[i]);
}
for (int i = 1; i <= n; i ++ )
if (res == max(up[i], d1[i]) && !(d & 1))
fail[i] = true;
while (q -- )
{
int a;
scanf("%d", &a);
if (fail[a]) puts("Bob");
else puts("Alice");
}
return 0;
}
EX.良序(GOODSEQUENCE)
前置知识:生成函数 EGF
对于很难求解的组合数学问题,我们采用生成函数,而生成函数只能解决常规组合问题,而解决排列问题我们要引入指数生成函数。
我们将 $A,B$ 的 $EGF$ 定义为 $f(x)$ 和 $g(x)$,则有:
$$f(x) = x + \frac{x^3}{3!} + \frac{x^5}{5!} + …$$
$$g(x) = 1 + \frac{x^2}{2!} + \frac{x^4}{4!} + …$$
使用泰勒展开收敛
$$f(x) = \frac{e^x+e^{-x}}{2}$$
$$g(x) = \frac{e^x-e^{-x}}{2}$$
于是我们的答案的 $EGF$ 就是它们的乘积
$$A(x) = (f(x)g(x))^n$$
$$ = (\frac{e^x+e^{-x}}{2})^n(\frac{e^x-e^{-x}}{2})^n $$
$$ = \frac{1}{2^{2n}}(e^{2x}-e^{-2x})^n$$
$$ = \frac{1}{2^{2n}}[\sum_{i=0}^{n}(-1)^iC_{n}^{i}e^{2x(n-i)-2xi}]$$
$$ = \frac{1}{2^{2n}}[\sum_{i=0}^{n}(-1)^iC_{n}^{i}e^{(2n-4i)x}]$$
而最终答案就是展开式的 $2n$ 次项系数,并乘上一个 $(2n)!$
$$Ans = (2n)![x^{2n}]A(x)$$
$$ = \frac{(2n)!}{2^{2n}}[\sum_{i=0}^{n}(-1)^iC_{n}^{i}\frac{(2n-4i)^n}{(2n)!}]$$
约去可以得到
$$ = \frac{1}{2^{2n}}[\sum_{i=0}^{n}(-1)^iC_{n}^{i}(2n-4i)^n]$$
于是我们就可以很愉快的敲代码啦!
记得记忆化输出答案,因为询问的 $q$ 远大于 $n$ 的值域,否则会 TLE 并获得 $70$ 分的好成绩。
时间复杂度 $O(n^2 + q\log^2 n)$ 。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5010;
const ll mod = 1e9 + 7;
ll n, C[N][N], Ans[N];
void init()
{
for (int i = 0; i <= 5000; i ++ ) C[i][0] = 1;
for (int i = 1; i <= 5000; i ++ )
for (int j = 1; j <= i; j ++ )
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
}
ll ksm(ll a, ll k)
{
if (!a) return 0;
ll res = 1;
while (k)
{
if (k & 1) res = res * a % mod;
k >>= 1;
a = a * a % mod;
}
return res;
}
int main()
{
int T;
scanf("%d", &T);
init();
memset(Ans, -1, sizeof Ans);
while (T -- )
{
scanf("%lld", &n);
if (~Ans[n]) printf("%lld\n", Ans[n]);
else
{
ll ans = 0, mul = ksm(2ll, n << 1);
mul = ksm(mul, mod - 2);
for (int i = 0; i <= n; i ++ )
{
ll res = C[n][i] * ksm((n << 1) - (i << 2), n << 1) % mod;
if (i & 1) ans = ((ans - res) % mod + mod) % mod;
else ans = (ans + res) % mod;
}
ans = ans * mul % mod;
Ans[n] = ans;
printf("%lld\n", ans);
}
}
return 0;
}