ARC145D 题解
y−x=z−y 这个东西转化成 2y=x+z。
先不管总和的限制,考虑三进制(为啥会想到这个啊),如果一个集合里面所有数字的三进制表示都没有 2(好像都没有 0 或者都没有 1 是一样的),那么这个集合一定合法,证明是显然的。
然后调整总和,记当前总和是 sum,如果 n∣m−sum 那么我们就可以直接偏移,但是不一定可以整除。
方法是先把最后一位都设成 0,然后根据余数把若干个调整成 1,这样就好起来了。
主要还是这个三进制的套路感觉比较神奇。
#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
int n,m,a[10001],cnt,sum;
inline bool check(int x)
{
while(x)
{
if(x%3==2)
return 0;
x/=3;
}
return 1;
}
signed main()
{
cin>>n>>m;
for(int i=0;cnt<n;++i)
if(check(i))
sum+=(a[++cnt]=3*i);
int p=(m%n+n)%n;
for(int i=1;sum%n!=p;++i)
{
++a[i];
++sum;
}
int d=(m-sum)/n;
for(int i=1;i<=n;++i)
cout<<a[i]+d<<" ";
cout<<'\n';
return 0;
}
峰峰峰の妙妙屋
怄火。挥手。转圈。街舞。跳跳。献吻。跳绳。激动。发抖。磕头。爱情。飞吻。左太极。右太极。回头。