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;
}
标签:02,ch,int,题解,CF1928E,项数,等差数列
From: https://www.cnblogs.com/operator-/p/18016157