专栏文章

AT_arc208_b [ARC208B] Sum of Mod 题解

cchenzhiyv
AT_arc208_b题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minjdk4k
此快照首次捕获于
2025/12/02 03:22
3 个月前
此快照最后确认于
2025/12/02 03:22
3 个月前
查看原文
AT_arc208_b [ARC208B] Sum of Mod 题解

前言

讲一种不用二分 a1a_1 的做法

解法

为了方便描述，记题目中的式子的值为 sumsum。
首先，因为取模，差最大为 ai−1−1a_{i-1}-1，所以我们要让 ana_n 尽量小，就要最小化前面的值，所以每次 aia_i 取 ai−1−1+ai−1a_{i-1}-1+a_{i-1} 即 2×ai−1−12 \times a_{i-1} -1 时最优。当后面 sumsum 的值等于 kk 时，令后面全部相等即可。
考虑现在 a1a_1 取什么值，当 a1a_1 为 11 时，11 于后面任何数都没有贡献，还占了一个位置，一定不优，所以 a1a_1 取 22。但是这样可能一因为长度限制而凑不够 kk，所以开始调整 a1a_1 的取值。
当 a1a_1 等于 22 时，序列为 2,3,5,9,…2,3,5,9,\dots，sum=(3−2)+(5−3)+(9−5)+⋯=1+2+4+⋯=2n+1−1sum=(3-2)+(5-3)+(9-5)+\dots = 1+2+4+\dots=2^{n+1}-1，nn 为这一串累加的长度。
当 a1a_1 为 33 时，序列为 3,5,9,17,…3,5,9,17,\dots，sum′=(5−3)+(9−5)+(17−9)+⋯=2+4+8+⋯=2×sumsum'=(5-3)+(9-5)+(17-9)+\dots=2+4+8+\dots =2 \times sum。
同理，当 aia_i 为 44 时，sum′′=3×sumsum''=3 \times sum。
所以 a1=⌈ksum⌉+1a_1=\lceil \frac {k}{sum} \rceil +1。 后面正常构造即可。

代码

CPP
#include<bits/stdc++.h>
#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
	char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
	template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
	inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
	inline void print(char x) { putchar(x); }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
	inline void print(bool b) { putchar(b+48); }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=2e5+10;
int n,k;
int a[N];
void init()
{
	for(int i=1;i<=n;i++)
		a[i]=0;
}
void solve()
{
	cin>>n>>k;
	init();
	int d=2;
	if(n<=31)
	{
		int sum=pow(2,n-1)-1;
		d=max(2ll,(int)ceil((double)k/(double)sum)+1);
	}
	a[1]=d;
	for(int i=2;i<=n;i++)
	{
		if(k>=a[i-1]-1)
		{
			if(a[i-1]==1)
				a[i]=a[i-1]*2;
			else
				a[i]=a[i-1]*2-1;
			k-=(a[i-1]-1);
		}
		else
		{
			a[i]=a[i-1]+k;
			k=0;
		}
	}
	for(int i=1;i<=n;i++)
		cout<<a[i]<<" ";
	cout<<endl;
}
signed main()
{
	int T;
	cin>>T;
	while(T--)
		solve();
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...