发现这个题的本质就是在做\(\rm hash\)

我们显然能够列出\(n\)个方程，之后高消，这是\(O(n^3)\)的

但是观察一下第一个和第二个方程

\[a_{1}26^{n-1}+a_{2}26^{n-2}+...+a_{n}26^{0}=b_1\]

\[a_{2}26^{n-1}+a_{3}26^{n-2}+...+a_{1}26^{0}=b_2\]

考虑让他们强行对齐一下，于是上面的方程乘\(26\)

即

\[a_{1}26^{n}+a_{2}26^{n-1}+...+a_{n}26^{1}=26b_1\]

相互减一下，中间那些对齐的项就消没了

\[a_126^0-a_126^{n}=b_2-26b_1\]

即\(a_1=\frac{b_2-26b_1}{1-26^n}\)，我们这样就能解出整个\(a\)了

之后发现在\(26^n\equiv 1(\rm mod\ p)\)的时候就崩了

我们发现如果\(b_1-a_1\times 26^n\equiv \frac{b_2-a_1}{26}(\rm mod\ p)\)，即\(26b_i-(1-26^n)a_1=b_{i+1}\)

因为\(26^n\equiv 1(\rm mod\ p)\)，所以这个时候\(26b_i\equiv b_{i+1}(\rm mod \ p)\)，又因为数据保证有解，所以我们只需要构造一个\(a\)，使得其满足\(a_{1}26^{n-1}+a_{2}26^{n-2}+...+a_{n}26^{0}=b_1\)即可，这样后面的自然也会满足

所以我们将\(b_1\)转成一个\(n\)位的\(26\)进制数即可

代码

#include
    
     #define re registerinline 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 int maxn=1e5+5;int n,p,mod;int pw[maxn],a[maxn],s[maxn];inline int ksm(int a,int b) {    if(a<0) a+=mod;    int S=1;    for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) S=1ll*S*a%mod;    return S;}namespace sub {    inline void solve() {        int x=a[0];        for(re int i=n-1;i>=0;--i) s[i]=x%26,x/=26;        for(re int i=0;i