C++14(g++5.4) 解法, 执行用时: 99ms, 内存消耗: 1240K, 提交时间: 2020-01-16 00:51:49
#include<bits/stdc++.h>
using namespace std;
int i,T,N,M=998244353;
int fastpow(long long a,int b)
{
long long s=1;
for(;b;a=a*a%M,b>>=1)if(b&1)s=s*a%M;
return s;
}
int main()
{
long long F[100005];
for(F[0]=i=1;i<100001;i++)F[i]=F[i-1]*(4*i-2)%M*fastpow(i+1,M-2)%M;
scanf("%d",&T);
for(i=1;i<=T;i++)
{
scanf("%d",&N);
printf("Case #%d: %d\n",i,(F[N]-F[N-1]+M)%M);
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 81ms, 内存消耗: 1252K, 提交时间: 2020-02-29 16:34:45
#include<bits/stdc++.h>
using namespace std;
int i,T,N,M=998244353;
int fastpow(long long a,int b)
{
long long s=1;
for(;b;a=a*a%M,b>>=1)
if(b&1) s=s*a%M;
return s;
}
int main()
{
long long F[100005];
for(F[0]=i=1;i<100001;i++)
F[i]=F[i-1]*(4*i-2)%M*fastpow(i+1,M-2)%M;
scanf("%d",&T);
for(i=1;i<=T;i++)
{
scanf("%d",&N);
printf("Case #%d: %d\n",i,(F[N]-F[N-1]+M)%M);
}
return 0;
}
Python3 解法, 执行用时: 710ms, 内存消耗: 8588K, 提交时间: 2022-05-26 12:38:09
l = [1, 1] + [0] * 100002
mod = 998244353
inv = lambda x: (mod - mod // x) * inv(mod % x) % mod if x - 1 else 1
for i in range(2,100002):
l[i] = l[i - 1] * (4 * i - 2) * inv(i + 1) % mod
t = int(input())
for i in range(t):
n = int(input())
print('Case #%d:' % (i+1), (l[n] - l[n - 1]) % mod)
和 
，它们是不同的当且仅当存在至少一个 
，使得 
。，且
不能第一个出栈。求合法的出栈序列个数。答案对
取模。
，表示蛙蛙有
， 表示目的地的个数（入栈元素个数）。
，具体可见样例。