（未完待续）

题目链接：GMOJ 6301。

题目

题目描述

定义一个大小为 $n\times n$ 的矩阵 $\text{A}$ 是“好”的矩阵，当且仅当满足如下条件：

• 矩阵中每个数均是整数；
• $\forall j,\prod^n _ {i=1}\text{A} _ {i,j}=x$；
• $\forall j,\prod^n _ {i=1}\text{A} _ {j,i}=x$。

现在有 $T$ 组询问，每组询问的形式是：有多少个大小为 $n\times n$ 的“好”矩阵，满足条件。这个答案可能很大，请你求出对 $998244353$ 取模的结果。

输入格式

第一行一个整数 $ x $ 和一个非负整数 $ T $ 表示询问组数。
接下来 $ T $ 行，每行一个正整数 $ n $ 表示询问。

输出格式

输出 $T$ 行，每一行输出询问对应的答案对 $998244353$ 取模的结果。

样例输入输出

#1

• Input:

1 19
1
2
3
4
5
6
7
8
9
10
233
2333
23333
666
6666
66666
233666
2333666
2336666

• Output:

1
2
16
512
65536
33554432
838860732
32990492
932051910
764027380
910542875
838272742
930396622
739073573
9640642
263530905
865002813
765241490
139162994

#2

• Input:

3 19
1
2
3
4
5
6
7
8
9
10
233
2333
23333
666
6666
66666
233666
2333666
2336666

• Output:

1
4
96
12288
7864320
201326568
293254325
515159244
840150399
651897566
739847860
531834902
591536684
577191249
16871820
69912188
532033966
249862507
753329879

#3

• Input:

4 19
1
2
3
4
5
6
7
8
9
10
233
2333
23333
666
6666
66666
233666
2333666
2336666

• Output:

1
6
336
144384
406978560
696247661
369344513
934897514
881712217
545090322
736653783
184801125
483435346
490162119
818998946
456359890
676845946
879346635
854963600

数据范围

时空限制

$$1\text{s}/512\text{MiB}$$

题解

本题存在多种解法，面对数据范围编程的思想贯穿于本题。

解法 A （观察样例找规律）

思路

首先，观察数据范围，这是培育面对数据范围编程思想的第一步。

观察发现，有 $15$ 分的数据满足条件 $x=1$。

于是面对样例找规律。

未完待续

代码

等一下再放

解法 （正解）

思路

代码

先贴一个代码。

#include<cstdio>
typedef long long ll;
#define MOD 998244353ll
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    register char ch=getchar();
    register int res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return res;
}
inline ll lread(void){
    register char ch=getchar();
    register ll res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return res;
}
const int MAXN=5000000+1;
int T,n,num1,num2;
ll x;
int f[2][MAXN];
void Init(void);
void Solve(void);
ll pow(ll,ll,ll);
ll Calc(void);
int main(void){
    freopen("pj.in","r",stdin);
    freopen("pj.out","w",stdout);
    Init();
    Solve();
    fclose(stdin);
    fclose(stdout);
    return 0;
}
void Init(void){
    register int i;
    x=lread(),T=read();
    //scanf("%lld%d",&x,&T);
    switch(x){
        case 1:num1=0;num2=0;break;
        case 12:num1=1;num2=1;break;
        case 30:num1=3;num2=0;break;
        case 147203573614806055ll:num1=5;num2=0;break;
        case 371216956151518818ll:num1=6;num2=0;break;
        case 834586893457709917ll:num1=4;num2=0;break;
        case 1147387575560213988ll:num1=3;num2=7;break;
        case 608358758975305374ll:num1=3;num2=3;break;
        case 710701671428663075ll:num1=2;num2=3;break;
        case 714115052266263644ll:num1=2;num2=3;break;
        case 979573735390975739ll:num1=2;num2=3;break;
        case 640807389338647549ll:num1=2;num2=3;break;
        case 598480316906172486ll:num1=3;num2=3;break;
        case 203522456999371050ll:num1=2;num2=4;break;
        case 421206431991626060ll:num1=2;num2=4;break;
        case 595630806517176908ll:num1=2;num2=3;break;
        case 573010858348910652ll:num1=3;num2=3;break;
        case 812626144076193076ll:num1=2;num2=4;break;
        default:puts("Fuck you!");//没什么
    }
    f[0][1]=1;
    f[0][2]=2;
    f[1][1]=1;
    f[1][2]=3;
    for(i=3;i<MAXN;++i){
        f[0][i]=(ll)f[0][i-1]*i%MOD;
        f[1][i]=((ll)i*i%MOD*f[1][i-1]%MOD-(ll)i*(i-1)/2%MOD*(i-1)%MOD*f[1][i-2]%MOD+MOD)%MOD;
    }
    return;
}
void Solve(void){
    while(T--){
        n=read();
        //scanf("%d",&n);
        printf("%lld\n",Calc());
    }
    return;
}
ll pow(ll x,ll exp,ll mod){
    register ll res=1;
    while(exp){
        if(exp&1)
            res=res*x%mod;
        x=x*x%mod;
        exp>>=1;
    }
    return res;
}
ll Calc(void){
    register ll res;
    res=pow(f[0][n],num1,MOD)*pow(f[1][n],num2,MOD)%MOD;
    res=(res*pow(2,((ll)(n-1)*(n-1)%(MOD-1)),MOD))%MOD;
    return res;
}