\(Description\)

求\(A_0,A_1,A_2,\cdots,A_{n-1}\)，满足

\[A_0*1^0+A_1*1^1+\ldots+A_{n-1}*1^{n-1}\equiv B[1](mod\ p)\]

\[A_0*2^0+A_1*2^1+\ldots+A_{n-1}*2^{n-1}\equiv B[2](mod\ p)\]

\[\ldots\ldots\ldots\]

\[A_0*n^0+A_1*n^1+\ldots+A_{n-1}*n^{n-1}\equiv B[n](mod\ p)\]

其中\(B[i]\)为\(str[i-1]\)表示的数字。

\(Solution\)

　　模意义下的高斯消元，在初等行变换时把\(t=tar(A[i][j])/Anow(A[j][j])\)改为\(t=tag*inv(Anow)\)。(也可以在tar不整除Anow时把tar变为它们的lcm，即整行乘\(lcm(tar,Anow)/tar\))

　　最后求解回带时把除法用乘逆元替代即可。(也可用扩展欧几里得求出一个最小的ans[i])

#include 
    
     #include 
     
      #include 
      
       #define mod ptypedef long long LL;const int N=100;namespace Gauss{    int p,n,A[N][N],ans[N];    char s[N];    int FP(LL x,int k)    {        LL t=1;        for(;k;k>>=1, x=x*x%p)            if(k&1) t=t*x%p;        return t;    }    inline int inv(int x) {return FP(x,p-2);}    void Init()    {        scanf("%d%s",&p,s);        n=strlen(s);        for(int i=0; i
       
        A[mxrow][j]) mxrow=i;            if(mxrow!=j) std::swap(A[mxrow],A[j]);            for(int i=j+1; i