正式赛1001 斐波那契

Problem Description

想必大家都很熟悉阶乘的概念。具体来说， n!=1×2×3⋯×n−1×n。
想必大家也很熟悉斐波那契数列的概念。具体来说，Fib[1]=1,Fib[2]=2,Fib[n]=Fib[n−1]+Fib[n−2]。
现在给出 n，请你算一算 Fib[1]×Fib[2]⋯×Fib[n−1]×Fib[n]的值。
由于这个值很大，请你输出答案除以 998244353的余数。

Input

第一行一个整数 T(1≤T≤20)，表示测试数据组数。接下来包含T组测试数据。
对于每组测试数据，输入一个数 n(1≤n≤2×10¹⁰)。

Output

对于每组测试数据，输出一个数，表示答案。

Sample Input

2
2
7351

Sample Output

2
560233622

比赛的时候我以为这是一道水题，可惜它不是，这道题很迷，数值过大的时候总是输出0，需要使用数论的方法解出来。

#include<iostream>
using namespace std;
int main()
{
    int T;
    cin>>T;
    for(int i=1;i<=T;i++)
    {
        int n;
        int qy=998244353;
        cin>>n;
        long long a[n];
        a[0]=1;a[1]=2;
        long long int kk=1;
        if(n==1)
        {
            cout<<a[0]%qy<<endl;
        }
        if(n==2)
        {
            cout<<a[1]%qy<<endl;
        }
        else if(n>=3)
        {
            for(int j=2;j<=n-1;j++)
            {
                a[j]=a[j-1]+a[j-2];
                a[j]=a[j]%qy;
                kk=kk*a[j];
                kk=kk%qy;
            }
            cout<<(kk*2)%qy<<endl;
        }
    }
    return 0;
}