# Code

const int XN=5e3+11;
const long long INF=1e18;

long long Mul(long long const &a,long long const &b) {
return (long double)a*(long double)b<INF?a*b:INF;
}

void Work() {
static int a[XN];
int n,m;long long k;
std::cin>>n>>m>>k;
++k;
static long long cnt[XN],pw2[XN]={1};
for(int i=1;i<=n;++i) {
std::cin>>a[i];
cnt[i]=1;
pw2[i]=Mul(pw2[i-1],2);
}
static long long sum[XN];
std::vector<int> Ans;
sum[0]=1;
for(int b=1;b<=n;++b) {
for(int i=1;i<=m;++i)
sum[i]=0;
for(int i=1;i<=n;++i)
Reduce(sum[a[i]]+=Mul(cnt[i],pw2[n-i]),INF);
int v=0;
while(k>sum[v])
k-=sum[v++];
if(v)
Ans.push_back(v);
else
break;
sum[0]=0;
if(a[n]==v)
sum[0]+=cnt[n];
for(int i=n;i>=1;--i)
sum[0]+=(cnt[i]=a[i-1]==v?cnt[i-1]:0);
for(int i=1;i<=n;++i)
Reduce(cnt[i]+=cnt[i-1],INF);
}
for(size_t i=0;i<Ans.size();++i)
std::cout<<Ans[i]<<(i==Ans.size()-1?'\n':' ');
}

int main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int T;std::cin>>T;
while(T--)
Work();
return 0;
}

# Solution

k次复单位根为w_k

\begin{aligned}
x^k-a^k&=a^k[(\frac xa)^k-1]\\
&=a^k\prod_{i=0}^{k-1}(\frac xa-w_k^i)\\
&=\prod_{i=0}^{k-1}(x-aw_k^i)
\end{aligned}

\begin{aligned}
\prod_{i=1}^n (x-a_iw_k^t)&=w_k^{tn}\prod_{i=1}^n (\frac {x}{w_k^t}-a_i)\\
&=w_k^{tn}\prod_{i=1}^n (\frac {x}{w_k^t}-a_i)\\
&=w_k^{tn}f(\frac {x}{w_k^t})
\end{aligned}

\begin{aligned}
\prod(x^k-a_i^k)&=\prod_{t=0}^{k-1}[w_k^{tn}f(\frac {x}{w_k^t})]\\
&=w_k^{\frac {nk(k-1)}2}\prod_{t=0}^{k-1}f(\frac x{w_k^t})
\end{aligned}

# Code

const int XN=20;
const long double pi=acos(-1.);

typedef std::vector<std::complex<long double>> Polynomial;

Polynomial operator *(Polynomial const &A,Polynomial const &B) {
Polynomial C(A.size()+B.size()-1,0);
for(size_t i=0;i<A.size();++i)
for(size_t j=0;j<B.size();++j)
C[i+j]+=A[i]*B[j];
return C;
}

int main() {
//  freopen("input","r",stdin);
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int n,m;
while(std::cin>>n>>m,n) {
static int a[XN];
std::complex<long double> root(cos(2*pi/m),sin(2*pi/m));
static std::complex<long double> w[XN];
for(int i=0;i<m;++i)
w[i]={cos(2*i*pi/m),sin(2*i*pi/m)};//w[i-1]*root;
for(int i=0;i<n;++i)
std::cin>>a[i];
a[n]=1;
Polynomial Ans{w[n*m*(m-1)/2%m]};
for(int t=0;t<m;++t) {
Polynomial f(n+1);
for(int i=0;i<=n;++i)
f[i]=std::complex<long double>(a[i])*w[((m-t*i)%m+m)%m];
Ans=Ans*f;
}
for(int i=0;i<n;++i)
std::cout<<std::fixed<<std::setprecision(0)<<Ans[i*m].real()<<(i==n-1?'\n':' ');
}
return 0;
}

# A

b-a\le 50，那么容易得出，当a较大时，给两个人的时间段数必须相同，否则不可能和相等。

const int XN=50+11;

int main() {
//freopen("input","r",stdin);
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int T;std::cin>>T;
while(T--) {
int n,a,b;std::cin>>n>>a>>b;
static int t[XN];
for(int i=1;i<=n;++i)
std::cin>>t[i];
if(a>2500) {
for(int i=1;i<=n;++i)
t[i]-=a;
static const int N=50,H=2500;
static int f[2][2*N+1][2*H+1];
memset(f[0],127,sizeof(f[0]));
f[0][N][H]=0;
for(int i=1,sum=0,o=1;i<=n;sum+=t[i++],o^=1) {
memset(f[o],127,sizeof(f[o]));
for(int j=-(i-1);j<=(i-1);++j)
for(int k=-sum;k<=sum;++k) {
int x=f[o^1][N+j][H+k];
if(k+t[i]<=H)
Reduce(f[o][N+j+1][H+k+t[i]],x);
if(k-t[i]>=-H)
Reduce(f[o][N+j-1][H+k-t[i]],x);
Reduce(f[o][N+j][H+k],x+1);
}
}
std::cout<<f[n&1][N][H]<<'\n';
} else {
static const int H=50*2500;
static int f[2][2*H+1];
memset(f[0],127,sizeof(f[0]));
f[0][H]=0;
for(int i=1,o=1,sum=0;i<=n;sum+=t[i++],o^=1) {
memset(f[o],127,sizeof(f[o]));
for(int j=-sum;j<=sum;++j) {
int x=f[o^1][H+j];
if(j+t[i]<=H)
Reduce(f[o][H+j+t[i]],x);
if(j-t[i]>=-H)
Reduce(f[o][H+j-t[i]],x);
Reduce(f[o][H+j],x+1);
}
}
std::cout<<f[n&1][H]<<'\n';
}
}
return 0;
}

# C

const int XN=1e5+11,P=1e9+7,INF=0x1f1f1f1f;

struct Edge {
int to;
unsigned int v;
};

std::vector<Edge> G[XN];

namespace StaticVertexBasedDC {
bool ud[XN];
int size[XN];

int GetSize(int pos,int fa) {
size[pos]=1;
for(auto &e : G[pos]) {
int u=e.to;
if(!ud[u] && u!=fa)
size[pos]+=GetSize(u,pos);
}
return size[pos];
}

int Centre(int pos) {
GetSize(pos,0);
int tot=size[pos];
bool found;
do {
found=0;
for(auto &e : G[pos])
if(!ud[e.to] && size[e.to]<size[pos] && size[e.to]*2>=tot) {
pos=e.to;
found=1;
break;
}
} while(found);
return pos;
}

long long Calc(std::pair<long long,unsigned int> a[],int n,std::array<int,32> const &xs) {
long long res=0;
for(int i=1;i<=n;++i) {
long long sum=0;
for(int b=31;b>=0;--b)
(sum+=(long long)(a[i].second>>b&1?n-xs[b]:xs[b])*(1u<<b))%=P;
(res+=a[i].first*sum)%=P;
}
return res;
}

std::pair<long long,unsigned int> all[XN],sub[XN];
std::array<int,32> aset,sset;
int allc,subc;
void DFS(int pos,int fa,long long len,unsigned int xs) {
sub[++subc]={len,xs};
for(auto &e : G[pos])
if(!ud[e.to] && e.to!=fa)
DFS(e.to,pos,(len+e.v)%P,xs^e.v);
}

int rec;

long long DC(int pos) {

static int cc;
++cc;
Enlarge(rec,cc);

ud[pos]=1;
allc=0;
long long res=0;
for(int i=0;i<32;aset[i++]=0);
for(auto &e : G[pos]) {
int u=e.to;
if(!ud[u]) {
for(int i=0;i<32;sset[i++]=0);
subc=0;

DFS(e.to,pos,e.v,e.v);
for(int i=1;i<=subc;++i)
for(int b=31;b>=0;--b)
sset[b]+=sub[i].second>>b&1;

(res-=Calc(sub,subc,sset))%=P;
for(int b=31;b>=0;--b)
aset[b]+=sset[b];
std::copy(sub+1,sub+1+subc,all+allc+1);
allc+=subc;
}
}
(res+=Calc(all,allc,aset))%=P;
for(int i=1;i<=allc;++i)
(res+=all[i].first*all[i].second%P)%=P;
for(auto &e : G[pos]) {
int u=e.to;
if(!ud[u])
(res+=DC(Centre(u)))%=P;
}

--cc;

return res;
}
}

void Work() {
int n;std::cin>>n;
using namespace StaticVertexBasedDC;
for(int i=1;i<=n;++i) {
ud[i]=0;
std::vector<Edge>().swap(G[i]);
}
for(int i=1;i<=n-1;++i) {
int x,y;unsigned int v;
std::cin>>x>>y>>v;
G[x].push_back({y,v});
G[y].push_back({x,v});
}

rec=0;

int Ans=DC(Centre(1));

//  std::cerr<<rec<<':'<<'\n';

Ans<0  && (Ans+=P);
std::cout<<Ans<<'\n';
}
int main() {
//freopen("input","r",stdin);
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int T;std::cin>>T;
while(T--)
Work();
return 0;
}

# E

const int XN=1e5+11,V=1e5;

int dsu[XN];
int Root(int x) {
return dsu[x]?dsu[x]=Root(dsu[x]):x;
}

void Work() {
int n;std::cin>>n;
static int cnt[XN];
for(int i=1;i<=V;++i)
cnt[i]=dsu[i]=0;
long long Ans=0;
for(int i=1;i<=n;++i) {
int x;std::cin>>x;
cnt[x]++;
}
for(int i=1;i<=V;++i)
if(cnt[i])
Ans+=(long long)(cnt[i]-1)*i;
for(int d=V;d>=1;--d) {
std::vector<int> v;
for(int x=d;x<=V;x+=d)
if(cnt[x])
v.push_back(x);
for(size_t i=0;i+1<v.size();++i)
if(Root(v[i])!=Root(v[i+1])) {
dsu[Root(v[i])]=Root(v[i+1]);
Ans+=d;
}
}
std::cout<<Ans<<'\n';
}

int main() {
//freopen("input","r",stdin);
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int T;std::cin>>T;
while(T--)
Work();
return 0;
}

# G

int C[21][21];
std::array<int,21> AddOne(std::array<int,21> const &a) {
std::array<int,21> res;
for(int i=0;i<=20;++i) {
res[i]=0;
for(int j=0;j<=i;++j)
(res[i]+=(long long)C[i][j]*a[j]%P)%=P;
}
return res;
}

std::array<int,21> &operator +=(std::array<int,21> &a,std::array<int,21> const &b) {
for(int i=0;i<=20;++i)
(a[i]+=b[i])%=P;
return a;
}

std::array<int,21> bit[XN];int n;
std::array<int,21> Sum(int pos) {
std::array<int,21> res;
for(int i=0;i<=20;res[i++]=0);
for(;pos;pos-=pos & -pos)
res+=bit[pos];
return res;
}

void Add(int pos,std::array<int,21> const &v) {
for(;pos<=n;pos+=pos & -pos)
bit[pos]+=v;
}

std::pair<int,int> p[XN];
std::vector<int> num;

int main() {
//freopen("input","r",stdin);
std::ios::sync_with_stdio(0);
std::cin.tie(0);
C[0][0]=1;
for(int i=1;i<=20;++i) {
C[i][0]=1;
for(int j=1;j<=i;++j)
C[i][j]=C[i-1][j-1]+C[i-1][j];
}
int T;std::cin>>T;
while(T--) {
std::vector<int>().swap(num);
int n,k;std::cin>>n>>k;
long long Ans=0;
for(int i=1;i<=n;++i) {
std::cin>>p[i].first>>p[i].second;
num.push_back(p[i].first);
}
std::sort(num.begin(),num.end());
num.erase(std::unique(num.begin(),num.end()),num.end());
for(int i=1;i<=(int)num.size()+1;++i)
for(int j=0;j<=20;bit[i][j++]=0);
::n=num.size()+1;
for(int i=1;i<=n;++i) {
p[i].first=std::lower_bound(num.begin(),num.end(),p[i].first)-num.begin()+2;
auto res=Sum(p[i].first-1),
for(int j=0;j<=20;++j)
v[j]=(long long)v[j]*p[i].second%P;
(Ans+=v[k])%=P;
}
std::cout<<Ans<<'\n';
}
return 0;
}

# J

const int XN=20;

int Pow(long long base,long long v,int P) {
long long res=1;
for(base%=P;v;v>>=1,(base*=base)%=P)
if(v&1)
(res*=base)%=P;
return res;
}

int Inverse(long long a,int P) {
return Pow(a,P-2,P);
}

long long Mul(long long x,long long y,long long P) {
long long res=0;
for(x%=P;y;y>>=1,(x*=2)%=P)
if(y&1)
(res+=x)%=P;
return res;
}

struct Lucas {
int P;
std::vector<int> fact,ifact;

Lucas(int P):P(P),fact(P),ifact(P) {
fact[0]=1;
for(int i=1;i<P;++i)
fact[i]=(long long)fact[i-1]*i%P;
ifact[P-1]=Inverse(fact[P-1],P);
for(int i=P-2;i>=0;--i)
ifact[i]=(long long)ifact[i+1]*(i+1)%P;
}

int C(int n,int m) {
return n<m?0:(long long)fact[n]*ifact[m]%P*ifact[n-m]%P;
}

int operator ()(long long n,long long m) {
long long res=1;
while(n && m) {
(res*=C(n%P,m%P))%=P;
n/=P,m/=P;
}
return res;
}
};

struct MultiLucas {
std::vector<Lucas> c;
std::vector<int> p,t;
std::vector<long long> r;
long long P;

MultiLucas(std::vector<int> const &p):p(p),t(p.size()),r(p.size()) {
P=1;
c.reserve(p.size());
for(size_t i=0;i<p.size();++i) {
P*=p[i];
c.emplace_back(p[i]);
}

for(size_t i=0;i<p.size();++i) {
r[i]=P/p[i];
t[i]=Inverse(r[i],p[i]);
}
}

long long operator ()(long long n,long long m) {
long long res=0;
for(size_t i=0;i<p.size();++i)
(res+=Mul((long long)c[i](n,m)*t[i]%P,r[i],P))%=P;
return res;
}
};

void Work() {
int n,k;
long long m;
std::cin>>n>>m>>k;
std::vector<int> p(k);
static long long v[XN];
long long all=0;
for(int i=0;i<n;++i) {
std::cin>>v[i];
all+=v[i];
}
long long P=1;
for(int i=0;i<k;++i) {
std::cin>>p[i];
P*=p[i];
}
MultiLucas C(p);
long long Ans=0;
for(int S=0;S<(1<<n);++S) {
int cnt=0;long long sum=0;
for(int i=0;i<n;++i)
if(S>>i&1) {
cnt++;
sum+=v[i]+1;
}
if(sum<=m) {
(Ans+=Mul(cnt&1?P-1:1,C(m-sum+n-1,n-1),P))%=P;
}
//  std::cerr<<S<<'\n';
}
std::cout<<Ans<<'\n';
}

int main() {
//freopen("input","r",stdin);
std::ios::sync_with_stdio(0);
std::cin.tie(0);
int T;std::cin>>T;
while(T--)
Work();
return 0;
}

# 非标准库的一些好用的东西

Bit Opearation Built-in Functions

int __builtin_ffs (int x)
//Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.
int __builtin_clz (unsigned int x)
//Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.
int __builtin_ctz (unsigned int x)
//Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.
int __builtin_clrsb (int x)
//Returns the number of leading redundant sign bits in x, i.e. the number of bits following the most significant bit that are identical to it. There are no special cases for 0 or other values.
int __builtin_popcount (unsigned int x)
//Returns the number of 1-bits in x.
int __builtin_parity (unsigned int x)
//Returns the parity of x, i.e. the number of 1-bits in x modulo 2.

# Code

int MinimumRepresentation(int *a,int n) {
++a;
int p1=0,p2=1,len=0;
while(p1<n && p2<n && len<n) {
if(a[(p1+len)%n]==a[(p2+len)%n])
len++;
else {
(a[(p1+len)%n]>a[(p2+len)%n]?p1:p2)+=len+1;
if(p1==p2)
p2++;
len=0;
}
}
return std::min(p1,p2)+1;
}