CF1928E题解

operator_ · 2024-02-15 12:37:22 · 题解

Modular Sequence

题目传送门

题解

发现 a_i+y 与 a_i\bmod y 均不改变 a_i 模 y 的余数，所以答案序列的每个元素均可表示为 x\bmod y+ky 的形式，先让 s 减去 n\times (x\bmod y)，再除以 y，这样原序列可以被划分为一个从 \lfloor\dfrac{x}{y} \rfloor 开始的等差数列和若干个从 0 开始的等差数列。

第一个等差数列可以直接枚举项数，后面的考虑预处理 dp，设 f_i 表示和为 i 的合法数列至少需要几项，转移枚举最后一个等差数列的项数，容易发现复杂度是 O(\sqrt n) 级别的。

最后还要输出方案，记录一下转移时最后一项的项数即可，是容易的。

代码：

/*
 * @Author: operator_ 
 * @Date: 2024-02-15 11:02:31 
 * @Last Modified by: operator_
 * @Last Modified time: 2024-02-15 12:36:34
 */
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int rd() {
    int s=0,m=0;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-')m=1;ch=getchar();}
    while( isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return m?-s:s;
}
int t,n,x,y,s,f[200005],g[200005];
signed main(){
    cin>>t;
    memset(f,0x3f,sizeof(f));f[0]=0;
    for(int i=1;i<=200000;i++)
        for(int j=1;(j-1)*j/2<=i;j++)
            if(f[i-(j-1)*j/2]+j<f[i]) 
                g[i]=j,f[i]=f[i-(j-1)*j/2]+j;
    while(t--) {
        n=rd(),x=rd(),y=rd(),s=rd();
        s-=n*(x%y);int xx=x/y,fl=0;
        if(s<0||s%y!=0) {puts("NO");continue;}
        s/=y;
        for(int i=1;i<=n&&(2*xx+i-1)*i/2<=s;i++) {
            int now=s-(2*xx+i-1)*i/2;
            if(f[now]+i<=n) {
                puts("YES");
                for(int j=1;j<=i;j++) printf("%lld ",x+j*y-y);
                for(int j=1;j<=n-f[now]-i;j++) printf("%lld ",x%y);
                while(now!=0) {
                    for(int j=1;j<=g[now];j++) printf("%lld ",x%y+j*y-y);
                    now-=(g[now]-1)*g[now]/2;
                }
                puts("");fl=1;break;
            }
        }
        if(!fl) puts("NO");
    }
    return 0;
}