魔法

solution

思路一

\(K\)是质数直接刚逆元,剩下的考虑用欧拉定理求解.

思路二

我们可以将所有数分解质因数然后记录每个质因数的指数求解.

100分

\(C_n^m=C_n^{m-1}\times\frac{n-m+1}{m}\).
根据欧拉定理:若\((a,p)=1\),则\(a^{\phi(p)}\equiv1(mod\;p)\)
所以对于与\(K\)互质的数,可以直接求逆元.
只要特别记录\(K\)的质因数的指数即可.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define K 7
#define N 400005
#define M 1000005
using namespace std;
typedef long long ll;
ll a[N],k,mul,ans,res=1ll;
int f[K],g[K],p[N],phi[M],ph,n,m,cnt;
bool b[M];
inline int read(){
    int ret=0;char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        ret=(ret<<1)+(ret<<3)+c-'0';
        c=getchar();
    }
    return ret;
}
inline void prime(int n){
    for(int i=2;i<=n;++i){
        if(!b[i]) p[++cnt]=i,phi[i]=i-1;
        for(int j=1;j<=cnt&&i*p[j]<=n;++j){
            b[i*p[j]]=true;
            if(!(i%p[j])){
                phi[i*p[j]]=phi[i]*p[j];
                break;
            }
            phi[i*p[j]]=phi[i]*(p[j]-1);
        }
    }
}
inline int tot(int n,int k){
    int ret=0;
    while(n>=k){
        ret+=n/k;n/=k;
    }
    return ret;
}
inline ll po(ll x,int k,ll p){
    ll ret=1ll;
    while(k){
        if(k&1) ret=ret*x%p;
        x=x*x%p;k>>=1;
    }
    return ret;
} 
inline ll c(int n,int m){
    if(!m||!(n-m)) return 1ll;
    ll ret=1;
    for(int i=1,t;i<=cnt&&p[i]<=n;++i){
        t=tot(n,p[i])-tot(m,p[i])-tot(n-m,p[i]);
        ret=ret*po(1ll*p[i],t,k)%k;
        if(!ret) return ret; 
    }
    return ret;
}
inline void Aireen(){
    n=read();k=1ll*read();
    for(int i=1;i<=n;++i)
        a[i]=1ll*read();
    prime(k);
    for(int i=1;i<=cnt;++i)
        if(!(k%p[i])) g[++m]=p[i];
    ans=a[1];ph=phi[(int)(k)]-1;
    for(int i=1,x;i