这题神仙的一批

看到乘法显然并不是很好做，尝试将其转化为加法

乘法变加法最常见的方式就是取\(log\)

\[\prod_{i=1}^na_i\equiv x(mod\ P)\]

就变成了

\[\sum_{i=1}^n log(a_i)\equiv log(x)(mod\ P)\]

但是在模意义下取\(log\)显然不是很可行啊

其实只需要找到一个合理的底数就好了

所以我们只需要找到原根就好了

如果\(g\)是\(P\)的原根，那么\(g^0,g^1,g^2....g^{\varphi(P)-1}\)这\(\varphi(P)\)个数肯定两两不同，又因为\(\varphi(P)=P-1\)，所以\(g\)的幂次方恰好能表示\(mod\ P\)意义下的所有整数

于是我们就把相乘转化成了指数相加

我们设一个多项式\(f(x)\)，\(f(x)\)表示\(x\)这个指数出现的次数

我们让\(f\)自己卷一下

\[f^2(x)=\sum_{i=0}^xf(i)f(x-i)\]

发现如果我们暴力\(dp\)求一下两个指数相加形成的方案也是这个柿子

于是我们就可以用卷积来代替暴力的背包\(dp\)

答案就是\(f^n(x)\)

需要一个多项式快速幂

代码

#include
    
     #include
     
      #include
      
       #include
       
        #define maxn 100005#define re register#define LL long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))inline int read() {    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;}const LL Mod=1004535809;const LL g[2]={3,334845270};int N,mod,T,n,len=1;int rev[maxn],tax[maxn];LL a[maxn],b[maxn],S[maxn],C[maxn];inline LL quick(LL a,LL b) {LL S=1;while(b) {if(b&1ll) S=S*a%Mod;b>>=1;a=a*a%Mod;}return S;}inline void NTT(LL *f,int o) {    for(re int i=0;i
        
         >1;LL og1=quick(g[o],(Mod-1)/i);        for(re int l=0;l
         
          >=1ll; mul(b,b); }}int main(){ N=read(),mod=read(),T=read(),n=read(); for(re int i=2;i
          
           >1]>>1)|((i&1)?len>>1:0); Quick(N); printf("%lld\n",S[tax[T]]); return 0;}