简单题*10086

Description

现有N个数c1,c2,...,cN。对于每个数求有多少个有序二元组(i,j)满足以下式子

ci * cj mod P=ck（i，j，k可想等）

其中P为一给定质数。对于每个k对应的答案记为cnt[k]，请你将每两个相邻的答案相加，这样答案总个数每次减少1，当答案个数为1时结束（结果对1e9+7取模）。为了感谢wjh、xxb、lmb、cly、ckx、yzj出了一堆简单题，请将他们名字缩写（小写）合并后去重并输出字典序第k大，k为所得结果乘上2333333后取模6666666的结果。

Input

第一行输入一个组数t（t ≤ 5）。

对于每组数据第一行有两个正整数N,P(1 ≤ N ≤ 100000，2 ≤ P ≤ 100000), P为质数。

第二行N个非负整数c1,c2,...,cN(0 ≤ ci ≤ 1e9)。

Output

输出共一行，为对应答案的字典序排列（答案为0输出-1）。

Sample Input

2 7 3 1 2 3 4 5 6 7 5 7 1 0 2 3 0

Sample Output

ckybhmwzxjl byjlhwzmckx

HINT

例如答案是1 2 3 4 5那么你应该经过以下变化变成一个答案

1 2 3 4 5

3 5 7 9

8 12 16

20 28

题解：

我们令g为质数P的原根，那么对于一个数字ai，唯一存在一个数字bi，使得。那么我们把所有的ai用这种形式表示，于是对于原本的式子ci*cj≡ck(mod P)，有，那么可以有bi+bj=bk。这样问题就从乘法变成了加法，FFT就可以排上用场了。而且你会发现，这里的bi的大小都是在P以内的。这样直接FFT即可，最后特殊处理一下0的情况即可。而对于接下来的一部可以发现最后结果就是C(n-1,0)*a[1]+C(n-1,1)*a[2]+……+C(n-1,n-1)*a[n]，可以O(n)求出答案，最后一步是个逆康托展开。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <bitset>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll inff = 0x3f3f3f3f3f3f3f3f;
#define FOR(i,a,b) for(int i(a);i<=(b);++i)
#define FOL(i,a,b) for(int i(a);i>=(b);--i)
#define REW(a,b) memset(a,b,sizeof(a))
#define inf int(0x3f3f3f3f)
#define si(a) scanf("%d",&a)
#define sl(a) scanf("%lld",&a)
#define sd(a) scanf("%lf",&a)
#define ss(a) scanf("%s",a)
#define mod ll(6666666)
#define pb push_back
#define eps 1e-6
#define lc d<<1
#define rc d<<1|1
#define Pll pair<ll,ll>
#define P pair<int,int>
#define pi acos(-1)
ll n,p,g,id[2000008],m,ans[5000008],pr[1000008],prime[1000008],qw[1000008],tot;
ll a[100008],jc[15],inv[100008],mm=1e9+7,vis[15],sss[100008];
char s[15],ss[5008];
inline int read()
{
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
void init(int n)
{
    int i,j;
    tot=0;
    prime[1]=1;
    for(i=2;i<=n;i++)
    {
        if(!prime[i]) prime[i]=pr[tot++]=i;
        for(j=0;j<tot&&pr[j]*i<=n;j++)
        {
            prime[i*pr[j]]=pr[j];
            if(i%pr[j]==0) break;
        }
    }
}
ll gmod(ll a,ll b,ll p)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%p;
        a=a*a%p,b>>=1;
    }
    return res;
}
int root(int x)
{
    int f,phi=x-1;qw[0]=0;
    for(int i=0;phi&&i<tot;i++)
    {
        if(phi%pr[i]==0)
        {
            qw[++qw[0]]=pr[i];
            while(phi%pr[i]==0) phi/=pr[i];
        }
    }
    for(int g=2;g<=x-1;g++)
    {
        f=1;
        for(int i=1;i<=qw[0];i++)
         if(gmod(g,(x-1)/qw[i],x)==1) {f=0;break;}
        if(f) return g;
    }
    return 0;
}
struct CP{
    double x,y;
    CP(){} CP(double a,double b):x(a),y(b){}
    CP operator+(const CP&r) const{return CP(x+r.x,y+r.y);}
    CP operator-(const CP&r) const{return CP(x-r.x,y-r.y);}
    CP operator*(const CP&r) const{return CP(x*r.x-y*r.y,x*r.y+y*r.x);}
}b[5000008],t;
inline void Swap(CP&a,CP&b) {t=a;a=b;b=t;}
inline void fft(CP*a,int f,int n)
{
    int i,j,k;
    for(i=j=0;i<n;i++)
    {
        if(i>j) Swap(a[i],a[j]);
        for(k=n>>1;(j^=k)<k;k>>=1);
    }
    for(int i=1;i<n;i<<=1)
    {
        CP wn(cos(pi/i),f*sin(pi/i));
        for(int j=0;j<n;j+=i<<1)
        {
            CP w(1,0);
            for(int k=0;k<i;k++,w=w*wn)
            {
                CP x=a[j+k],y=w*a[i+j+k];
                a[j+k]=x+y;a[i+j+k]=x-y;
            }
        }
    }
    if(f==-1) FOR(i,0,n) a[i].x/=n;
}
void rkt(ll n,ll k)
{
    ll t,ty=0;
    REW(vis,0);
    n--;
    FOR(i,0,k-1)
    {
        t=n/jc[k-i-1];
        n%=jc[k-i-1];
        for(ll j=0,pos=0;;j++,pos++)
        {
            if(vis[pos]) j--;
            if(j==t){vis[pos]=1;s[ty++]=('a'+pos+1);break;}
        }
    }
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    freopen("date1.in","r",stdin);
    freopen("date1.out","w",stdout);
    int tt;
    cin>>tt;
    ss['b']='b',ss['c']='c',ss['d']='h',ss['e']='j',ss['f']='k',ss['g']='l';
    ss['h']='m',ss['i']='w',ss['j']='x',ss['k']='y',ss['l']='z';
    jc[0]=jc[1]=1;
    for(ll i=2;i<=12;i++) jc[i]=jc[i-1]*i;
    inv[1]=1;
    FOR(i,2,100005)  inv[i]=(mm-mm/i)*inv[mm%i]%mm;
    init(100000);
    while(tt--)
    {
        cin>>n>>p;
        g=root(p);
        ll tmp=1,qw=0,er,sum=1;
        for(int i=1;i<p-1;i++)
        {
            tmp=tmp*g%p;
            id[tmp]=i;
        }
        er=m=p-1;
        for(m=er+m,er=1;er<=m;er<<=1);
        FOR(i,0,er+1) b[i].x=b[i].y=0.0,ans[i]=0;
        FOR(i,1,n)
        {
            a[i]=read();
            if(!(a[i]%p)) qw++;
            else b[id[a[i]%p]].x+=1.0;
        }
        fft(b,1,er);
        FOR(i,0,er) b[i]=b[i]*b[i];
        fft(b,-1,er);
        for(int i=0;i<2*p;i++) ans[i%(p-1)]+=(ll)(b[i].x+0.2);
        for(int i=1;i<=n;i++)
        {
            if(a[i]>=p) er=0;
            else if (a[i]==0) er=2*qw*n-qw*qw;
            else er=ans[id[a[i]]];
            sss[i]=er;
        }
        er=0;
        for(int i=0;i<n;i++)
        {
            er=(er+sum*sss[i+1])%mm;
            sum=(sum*(n-1-i)%mm)*inv[i+1]%mm;
        }
        //cout<<er<<endl;
        er=((er%mod)*2333333)%mod;
        if(er==0) {puts("-1");continue;}
        rkt(er,11);
        for(int i=0;i<11;i++) printf("%c",ss[s[i]]);
        puts("");
    }
    return 0;
}