自动搬运

查看原文

来自洛谷，原作者为

	WYXkk Zzz Zzz

搬运于2025-08-24 22:22:23，当前版本为作者最后更新于2020-11-11 13:41:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

在 MO 课上听到了和这题类似的题，所以跑来写篇题解（

首先发现一个性质：我们必须保证任何时刻 $a_i\le i$。

否则，一旦 $a_i>i$，那么我们再也无法对 $a_i$ 操作，它就不可能降为 $0$。

因此，每次一定是选择 $a_i=i$ 的最小 $i$ 操作。

因此我们可以把整个过程反过来，相当于每次选择最小的 $i$ 使 $a_i=0$，然后 $a_1,a_2,\cdots,a_{i-1}$ 全部减一，$a_i$ 变成 $i$。

然后通过模拟这个过程可以拿到 35pts 的好成绩。

接下来我们可以考虑找规律，因此打个表。

打表程序 ↓

const int N=3000005;
int a[N];
int main()
{
	freopen("out.txt","w",stdout);int n=0;
	F(i,1,999)
	{
		printf("%3d:",i);
		int u=1;while(a[u]){--a[u];++u;}a[u]+=u;
		if(u>n) n=u;
		F(j,1,n) printf("%d ",a[j]);puts("");
	}
	return 0;
}

然后打出来的表大概长这样 ↓（截取了一部分）

  1:1 
  2:0 2 
  3:1 2 
  4:0 1 3 
  5:1 1 3 
  6:0 0 2 4 
  7:1 0 2 4 
  8:0 2 2 4 
  9:1 2 2 4 
 10:0 1 1 3 5 
 11:1 1 1 3 5 
 12:0 0 0 2 4 6 
 13:1 0 0 2 4 6 
 14:0 2 0 2 4 6 
 15:1 2 0 2 4 6 
 16:0 1 3 2 4 6 
 17:1 1 3 2 4 6 
 18:0 0 2 1 3 5 7 
 19:1 0 2 1 3 5 7 
 20:0 2 2 1 3 5 7 
 21:1 2 2 1 3 5 7 
 22:0 1 1 0 2 4 6 8 
 23:1 1 1 0 2 4 6 8 
 24:0 0 0 4 2 4 6 8 
 25:1 0 0 4 2 4 6 8 

每一位似乎都有循环节，但是这个循环节随着数增大越来越长，非常难受，很难处理。

事实上是，我们找规律的对象选错了。

我们可以对每次操作的 $a$ 找规律，得到下面这张表 ↓（截取了一部分）

$1,2,1,3,1,4,1,2,1,5,1,6,1,2,1,3,1,7,1,2,1,8,1,4,1,2,1,3,1,9,1,2,1,10,1,5$

每两个出现一个 $1$，每六个出现一个 $2$。还有其它规律吗？

我们去掉所有 $1$：$2,3,4,2,5,6,2,3,7,2,8,4,2,3,9,2,10,5,2,3,11,2,4,12,2,3,6,2,13,14,2,3,4$

现在是每三个一个 $2$，我们再去掉所有 $2$：$3,4,5,6,3,7,8,4,3,9,10,5,3,11,4,12,3,6,13,14,3,4,5,7,3,15,16,4,3,8,6,5,3,1$

剩下的是每四个一个 $3$，我们再去掉所有 $3$：$4,5,6,7,8,4,9,10,5,11,4,12,6,13,14,4,5,7,15,16,4,8,6,5,17,4,18,9,19,7$

剩下的是每五个一个 $4$，后面以此类推。

因此，我们得到规律：$\ge m$ 的操作中，第一个操作 $m$，后面每 $m+1$ 次操作一次 $m$。

仔细想想会发现这个规律是显然成立的。也就是说规律发现比规律证明难？

因此我们只需要想办法定下 $n$ 的值，然后就能 $O(n)$ 定出每个数被操作多少次，然后就可以用前缀和搞一下得出所有数最终值。

至于 $n$ 值怎么定？先本地二分打表，求出一些 $n$ 对应的最小 $s$；然后查表，求出 $s$ 对应的 $n$ 在哪个范围内；然后在这个范围内二分求出 $s$ 对应的 $n$。

然后这题就做完了。

参考代码：

打表 ↓

const int N=3000005;
int a[N];
int check(ll s)
{
	int i=1;while(s){s=s*i/(i+1);++i;}
	return i;//这里似乎写错了，但也过了？/yun
}
ll doit(int n)
{
	ll l=1,r=2000000000000ll;
	while(l!=r)
	{
		ll mid=(l+r)>>1;
		if(check(mid+n)>=n) r=mid;else l=mid+1;
	}
	return l;
}		
int main()
{
	freopen("out.txt","w",stdout);
	F(i,1,200) printf("%lldll,",doit(i*10000));
	return 0;
}

最终程序 ↓

const int N=3000005;
ll tmp[]={/*表省略*/};
ll a[N],b[N];
int check(ll s)
{
	int i=1;while(s){s=s*i/(i+1);++i;}
	return i-1;
}
int doit(ll a,int l,int r)
{
	while(l!=r)
	{
		int mid=(l+r)>>1;
		if(check(a+mid)<=mid) r=mid;else l=mid+1;
	}
	return l;
}
int main()
{
	ll s=rd();
	int i=1;while(s>=tmp[i]) ++i;
	int n=doit(s,(i-1)*10000,i*10000);
	printf("%d\n",n);s+=n;
	F(i,1,n) {ll u=s*i/(i+1);a[i]=s-u;s=u;}
	F(i,1,n) b[i]=a[i]*i;
	UF(i,n,2) {b[i-1]-=a[i];a[i-1]+=a[i];}
	F(i,1,n) printf("%lld ",b[i]);
	return 0;
}