「题解」普及组 pj

(未完待续)

题目链接: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

数据范围

数据标号 $ T \leq $ $ x = $ $ \max \{ n \} \leq $
1 12 5
2 30 5
3 1
4 1
5 1
6 147203573614806055
7 371216956151518818
8 834586893457709917
9 10 1147387575560213988 2000
10 608358758975305374 2000
11 710701671428663075 2000
12 714115052266263644 2000
13 10 979573735390975739 300000
14 640807389338647549 300000
15 598480316906172486 300000
16 203522456999371050 300000
17 421206431991626060
18 595630806517176908
19 573010858348910652
20 812626144076193076

时空限制

$$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;
}