水题解来了
开始讲题
一步一步来吧，先是(50pt)
(first--50pt)
话说这个部分应该都会吧
其实这个部分就是把所有能想到的做法都拿出来爆搞就是了，比如存储后排序再扫描处理，或者直接用桶存
而我们现在关心的是后一种做法。为什么？我也不知道，因为这与我们之后的(75pt)以及正解的思路都密切相关。而(50pt)部分的桶做法应该都能想到吧，就是用个(map)暴力存储，再看最后的出现次数是否(mod~k)为零
(second--75pt)
可是(map)到了第二个部分(75pt)时，(8mb)会卡得你不要不要的，所以就只能考虑其它的奇技淫巧了
依旧考虑桶的思路，而目标是优化空间，那么就考虑将一个数拆成其(k)进制的若干部分，比如(k=3)时，将((5)_ {10})变成((12)_ {3})，而将((12)_ {3})的个位(2)存入专门存个位的桶中，十位(1)存入专门存十位的桶中，这个存其实就是将数加入桶中。而将桶取模(k)，若有剩余那么剩下的必然是可以计入答案中的，关于这个我们假设混入的魔导书为(t)，其存入的某一位设为第(p)位，则其存入的数值是(ans_p=frac{t\% k^{p+1}}{k^p})，而显然(k^p<t\%k^{p+1}<k^{p+1})，所以(0<ans_p<frac{k^{p+1}}{k^p}=k)（以上除号均是下取整），所以膜(k)后剩下的值一定是答案中的，可以加入
也就是以下代码：
fac[0]=1;
for(register int i=1;fac[i-1]<=lim;up=i++)
fac[i]=fac[i-1]*k;
for(register ll x;n;--n)
{
x=read();
for(register int i=up;x;--i)
if(x>=fac[i])
{
ans[i]+=x/fac[i];
if(ans[i]>=k)
ans[i]-=k;
x%=fac[i];
}
}
for(register int i=up;~i;--i)
res+=ans[i]*fac[i];
只给出了一部分，其中(fac_i=k^i)，而(res)就是最后答案
(third--100pt)
而第二部分的空间(O(log_2a_{max}))是合格了，但显然时间(O(nlog_ka_{max}))被卡掉了，所以考虑进一步优化
继续考虑桶与拆分的思路，可以想到把(second)中的空间稍微开大一点以达到节约时间的目的
将一个数分成若干个部分，但这次不是统计那个部分的代数和了，而是统计某个数的该部分的出现次数，这样就可以成功解决问题了
比如将一个数(a)分为(a_{1-8})的(8)个部分，其中(2^{8* (i-1)}<=a_i<2^{8* i})，那么再建立(8)个数组(ans_{i,j})，其中(ans_{i,a_i})自加，那么这些数组就跟一个个小桶一样了，时间也节约了很多，只是(O(n))套了一个(8)的常数，而能顺利解决问题
至于开(8)个数组只是怕(MLE)，其实应该可以开更小的，但(8)个已经够了，不会(T)
短小精悍的代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read()
{
ll x=0,ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar());
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return x;
}
const int digit=1<<8,p=8;
int a[p][digit];
ll ans,n,k;
int main()
{
n=read(),k=read();
for(register ll x;n;--n)
{
x=read();
for(register int i=0;i<p;++i)
++a[i][(x>>(i*p))&(digit-1)];
}
for(register ll i=1;i<digit;++i)
for(register int j=0;j<p;++j)
if(a[j][i]%k)
ans+=(i<<(j*p));
printf("%lld
",ans);
return 0;
}