牛客OI周赛15-提高组B题

图片说明
仅对官方题解一个比较（通俗??)的理解
题解：当 $n-2|(x-1)$ 时有解
证明：显然，求得序列中 $a_2,a_3\cdots a_n$ 中，若给其从小到大排个序，那么前 $x$ 个数必然是相同的,则有 $\sum\limits_{i=2}^{i=x+1}x^{a_i}=\sum\limits_{i=2}^{i=x+1}x^{a_2}=x^{a_2+1}$
那么如果对于给定的 $(n,x)$ 有解的话，必然使得 $(n-x-1,x)$ 有解，其实就是把（ $n,x$ ）这组合法序列的 $a_2\cdots a_{x+1}$ 替换成 $a_2+1$ 就是新的合法序列了。
那么可以递归下去 $(n-k*(x-1),x)$ ， $k=0,1,2\cdots$ 都是合法序列。
显然 $n<x+1$ && $n!=2$ 时无解，所以递减到最后只能是 $x+1$ ;
即有 $n-k*(x-1)=x+1$ 解得 $n-2=(k+1)*(x-1)$ ,即 $n-2|(x-1)$
得证。
构造办法,从上述可知， $n-1=x+k*(x-1)$ ，那么构造办法就可以为第一个为 $\frac{(n-1-x)}{(x-1)}+1$ ,接下来x个0，接下来x-1个为1，x-1个为2...
代码

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
using namespace std;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int n,x;
    cin>>n>>x;
    int t=(n-x-1)/(x-1)+1;
    cout<<t<<" ";
    for(int i=1;i<=x;i++)
        cout<<0<<" ";
    int res=1;
    for(int i=1;i<=n-x-1;i++)
    {
        if(i%(x-1)==0)cout<<res++<<" ";
        else cout<<res<<" ";
    }
    cout<<endl;
}