D. Make Equal
题意：给定 \(n\) 个正整数 \(a_1,a_2,...,a_n\)，每次操作可以给一个 \(a_i\) 加上 \(2\) 的一个非负整数次幂，问最少多少次使得全同。
题解：很妙啊！感觉非常没有办法往那个方面想，但只要想就能柳暗花明。
首先把 \(a\) 排序，然后 \(a_i\to a_n-a_i\)，问题转化为了最小化 \(\sum \text{popcount}(x+a_i)\)。
按位考虑，发现描述进位情况看似需要 \(2^n\)，实则一定是按 \(a_i\%2^w\) 排序的一个后缀。
于是状态数变为 \(O(n\log n)\)，时间复杂度因为要排序再多一个 \(\log\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
const int mod=1e9+7;
#define int long long
#define inf 1e12
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int n,m,a[maxn],dp[maxn],tmp[maxn],b[maxn],id[maxn],lid[maxn],vis[maxn],ans=inf;
inline int cmp(int x,int y){return b[x]==b[y]?x<y:b[x]>b[y];}
signed main(){
n=read();
for(int i=1;i<=n;i++)a[i]=read(),id[i]=i,dp[i]=inf;
sort(a+1,a+1+n);for(int i=1;i<=n;i++)a[i]=a[n]-a[i];
for(int i=0;i<60;i++){
for(int j=1;j<=n;j++)b[j]=(a[j]%(1ll<<i)),id[j]=j;
sort(id+1,id+1+n,cmp);int c1=0,c2=0,c3=0;
for(int j=1;j<=n;j++)if(a[j]>>i&1)c1++;
for(int j=0;j<=n;j++)tmp[j]=dp[j],dp[j]=inf;
for(int j=0;j<=n;j++){
if(j){
if(a[id[j]]>>i&1)++c3;
else ++c2;
}dp[c3]=min(dp[c3],tmp[j]+c1+c2-c3);
}c3=c1,c2=n-c1;
for(int j=0;j<=n;j++){
if(j){
if(a[id[j]]>>i&1)++c2;
else --c2,++c3;
}dp[c3]=min(dp[c3],tmp[j]+c2);
}
}for(int i=0;i<=n;i++)
ans=min(ans,dp[i]+i);
printf("%lld\n",ans);
return 0;
}
E. Problem from Red Panda
题意：有一个序列 \(a_1,a_2,...,a_k(\sum a_i\leqslant 10^6)\)。
一次操作是选择一个 \(i\)，若其他都为正，则 \(\forall j\neq i,a_j\to a_j-1,a_i\to a_i+k-1\)。
求通过操作能达到的不同状态数。
题解：考虑最终我们给颜色 \(i\) 操作了 \(x_i\) 次，令 \(s=\sum x_i\)。
注意到最终每个颜色的个数为 \(a_i+x_in-s\)，注意到把 \(x_i\) 同时减 \(1\) 上式是不变的。
所以我们其实就是要计数 \(\{x_k\}\) 的个数，且最小值为 \(0\)。
很多题解还讨论了这个的正确性，但是我只能说，看到这有问题的同学，你再读读题吧。
考虑一个 \(\{x_k\}\) 的可行性。首先 \(a_i+x_in-s\geqslant 0\to x_i\geqslant \lceil \frac{\max\{s-a_i,0\}}{k}\rceil\)。
于是我们得到了一个不等关系：\(s=\sum x_i\geqslant \sum \lceil \frac{\max\{s-a_i,0\}}{k}\rceil\)。
不难发现这个式子与 \(x_i\) 无关，而且 \(\forall t\leqslant s\) 都也应当满足上式。
只要满足这个条件 \(\{x_k\}\) 的操作顺序是容易构造的。
注意到若 \(s>a_{\max}\) 则 \(x_{\min}>0\)，故 \(s\) 只需枚举到 \(a_{\max}\) 即可。
于是我们枚举 \(s\) 剩下就是一个插板的事情。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e6;
const int maxn=2e6+10;
const int mod=998244353;
#define inf 1e9
inline int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
int fac[maxn],ifc[maxn],inv[maxn];
inline int com(int x,int y){
if(x<0||y<0||x<y)return 0;
return 1ll*fac[x]*ifc[y]%mod*ifc[x-y]%mod;
}
inline int calc(int x,int y){return com(x+y-1,x);}
int n,k,A[maxn],C[maxn],ans;
int main(){
k=read();fac[0]=ifc[0]=inv[1]=1;
for(int i=1;i<=k;i++)A[i]=read(),n+=A[i];
for(int i=2;i<=N;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(int i=1;i<=N;i++)fac[i]=1ll*fac[i-1]*i%mod;
for(int i=1;i<=N;i++)ifc[i]=1ll*ifc[i-1]*inv[i]%mod;
sort(A+1,A+1+k);int w=0;
for(int S=0,p=1;S<=A[k];S++){
while(A[p]<S)++C[A[p]%k],++p;
w+=C[(S-1+k)%k];if(w>S)break;
ans=(ans+calc(S-w,k)-calc(S-w-(k-p+1),k))%mod;
}printf("%d\n",(ans+mod)%mod);
return 0;
}