(未完待续)
题目链接: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;
}
近期评论