题目

正解

随便生成函数，显然答案为$(\prod (1+x^{t_i}){)}^m$
外面的这个乘方可以直接快速幂，时间复杂度$O(e\lg e\lg m)$。
重点是如何计算里面的这个东西。

由于$\sum t_i\le 2e7$，所以不同的$ti$的个数大概是$\sqrt{\sum t_i}$，约等于$6000$。
将$t_i$相同的一起计算，用个组合数就可以做到$O(个数)$处理，然后花$O(\sqrt{\sum t_i}e\lg e)$的时间来将$t_i$不同的合并起来。
然而常数太大TLE了……
这时候可以想到当个数比较少的时候，直接暴力做。
定义一个阈值，理论上这个阈值设$\lg e$最优，实际上这只有85分。
跑个大数据，然后手动三分一下阈值，发现当这个阈值设为$1000$的时候跑得最快。
于是就过了……

当然上面那样做是水法。
正解是一个见过一次就可能不会忘的小科技。
考虑这题本质上就是做一个长度为$e$的循环卷积。题目给出的$x$显然就是$e$次单位根（$x^e\equiv (\mathrm{m}\mathrm{o}\mathrm{d}p)$）。
如果我们求出了长度为$e$的$DFT$，在这个$DFT$上操作一波之后再$IDFT$回去，那就可以达到一个优秀的时间复杂度。

现在的问题是如何求这个东西：（注意我们平常求的$DFT$要将长度凑到$2^k$形式的，这样算的循环卷积就是$2^k$长度的循环卷积，和我们要求的不同）
记单位根为${\omega }_e$（就是题目的$x$），我们要求$F({\omega }_e^k)$，其中$k\in [0,e)$
$$\begin{gathered} F({\omega }_e^k)=\sum _{i=0}^{e-1}{a}_i{\omega }^{ik} \\ =\sum _{i=0}^{e-1}{a}_i{\omega }_e^{\frac{k^2+i^2-(k-i{)}^2}{2}} \\ =\sum _{i=0}^{e-1}{a}_i{\omega }_{2e}^{k^2+i^2-(k-i{)}^2} \\ ={\omega }_{2e}^{k^2}\sum _{i=0}^{e-1}{a}_i{\omega }_{2e}^{i^2}{\omega }_{2e}^{-(k-i{)}^2} \end{gathered}$$
后面的显然是个卷积，于是NTT即可（这个NTT和我们这里说了求长度为$e$的DFT没有什么关系，不要混淆……）
不过有时候${\omega }_e$没有平方根，那么还有另一种拆分方式：
$$\begin{gathered} F({\omega }_e^k)=\sum _{i=0}^{e-1}{a}_i{\omega }^{ik} \\ =\sum _{i=0}^{e-1}{a}_i{\omega }_e^{C_{k+i}^2-C_k^2-C_i^2} \end{gathered}$$
同样可以求得。
至于$IDFT$，用${\omega }^{-1}$代进去，最终结果乘$e^{-1}$即可。

对于这题，直接套用这个做法可以得到和暴力差不多的时间（除快速幂部分外，快速幂部分直接在点值上快速幂）。
这题有个更简单的实现方式：对于一个$1+x^{t_i}$，直接将${\omega }_e^k,k\in [0,e)$代进去，就可以快速地计算出它的$DFT$。然后它的乘方就直接在点值上乘方，接着将$t_i$不同的按对应的位置乘在一起，再把每个位置取$m$次方，最后$IDFT$回来。
于是真正需要实现上面这个算法的部分就只有一次$IDFT$啊……

代码

水法

using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define N 1000010
#define mo 998244353
#define E 131072
#define T 20000000
#define ll long long
ll qpow(ll x,int y=mo-2){ll r=1;for (;y;y>>=1,x=x*x%mo)if (y&1)r=r*x%mo;return r;
}
int n,m,x,e;
int t[N];
int nN,re[E],w[E];
void setlen(int n){int bit=0;for (nN=1;nN<=n;nN<<=1,bit++);re[0]=0;for (int i=1;i<nN;++i)re[i]=re[i>>1]>>1|(i&1)<<bit-1;
}
void clear(ll A[],int n){memset(A,0,sizeof(ll)*n);
}
void dft(ll A[],int flag){for (int i=0;i<nN;++i)if (i<re[i])swap(A[i],A[re[i]]);for (int i=1;i<nN;i<<=1){ll wn=qpow(3,(flag==1?(mo-1)/(2*i):mo-1-(mo-1)/(2*i)));w[0]=1;for (int k=1;k<i;++k)w[k]=(ll)w[k-1]*wn%mo;for (int j=0;j<nN;j+=i<<1)for (int k=0;k<i;++k){ll x=A[j+k],y=w[k]*A[j+k+i];A[j+k]=(x+y)%mo;A[j+k+i]=(x-y+(ll)mo*mo)%mo;}}if (flag==-1){ll invn=qpow(nN);for (int i=0;i<nN;++i)A[i]=A[i]*invn%mo;}
}
void multi(ll c[],ll a[],ll b[],int n){static ll A[E],B[E];setlen(n*2);clear(A,nN);for (int i=0;i<n;++i)A[i]=a[i];dft(A,1);if (a!=b){clear(B,nN);for (int i=0;i<n;++i)B[i]=b[i];dft(B,1);for (int i=0;i<nN;++i)c[i]=A[i]*B[i]%mo;}else{for (int i=0;i<nN;++i)c[i]=A[i]*A[i]%mo;}dft(c,-1);for (int i=n;i<nN;++i){(c[i-n]+=c[i])%=mo;c[i]=0;}
}
ll fac[N],ifac[N];
ll C(int m,int n){return fac[m]*ifac[n]%mo*ifac[m-n]%mo;}
ll F[E],G[E],H[E];
struct Ans{int a,b;
} ans[N];
int cnt;
bool cmpa(Ans x,Ans y){return x.a<y.a;}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);freopen("number.in","r",stdin);freopen("number.out","w",stdout);scanf("%d%d%d",&n,&m,&x);for (int i=1,pw=x;i<=50000;++i,pw=(ll)pw*x%mo)if (pw==1){e=i;break;}fac[0]=1;for (int i=1;i<=n;++i)fac[i]=fac[i-1]*i%mo;ifac[n]=qpow(fac[n]);for (int i=n-1;i>=0;--i)ifac[i]=ifac[i+1]*(i+1)%mo;	for (int i=1;i<=n;++i)scanf("%d",&t[i]);sort(t+1,t+n+1);H[0]=1;int B=/*log2(e)*/1000;for (int i=1,j=1;i<=n;++i)if (t[i]!=t[i+1]){int l=i-j+1;if (l>B){for (int k=0;k<=l;++k)F[(ll)k*t[i]%e]+=C(l,k);multi(H,H,F,e);for (int k=0;k<=l;++k)F[(ll)k*t[i]%e]=0;}else{while (l--){for (int k=e-1;k>=0;--k)(H[k+t[i]]+=H[k])%=mo;for (int k=e-1+t[i];k>=e;--k)(H[k-e]+=H[k])%=mo,H[k]=0;}}j=i+1;}G[0]=1;for (;m;m>>=1,multi(H,H,H,e))if (m&1)multi(G,G,H,e);for (int i=0,pw=1;i<e;++i,pw=(ll)pw*x%mo){int a=pw,b=G[i];if (b)ans[++cnt]={a,b};}sort(ans+1,ans+cnt+1,cmpa);for (int i=1;i<=cnt;++i)printf("%d %d\n",ans[i].a,ans[i].b);return 0;
}