Codeforces Round #740 D2 (Div. 2, based on VK Cup 2021 - Final (Engine))Problem - D2 - Codeforces

题意：

有 \(n\) 个数，从 \(1\) 到 \(n\) 排列，当你处在一个位置 \(x(x>1)\) 时，你可以执行如下操作

1.选一个数 \(y\ (1\le y\le x-1)\)，到达位置 \(x-y\) 处

2.选一个数 \(y\ (2\le y\le x)\)，到达位置 \(\lfloor \frac{x}{y}\rfloor\)处

现问从一个位置 \(n\) 要走到 \(1\) 共有多少种不同的方案，对一个给定的模数取模。

\(2\le n\le 4\times10^6\)

思路：

分开处理两种操作的贡献，加起来即可

对于1操作，只用处理前缀和即可，麻烦的是操作2

思路1：考虑整除分块，处理y可能到的取值，复杂度\(O(n\sqrt{n})\)

但这题明显卡根号，要想出log的做法，感觉之前遇到过类似的情况

[Harbour.Space Scholarship Contest 2021-2022 (open for everyone, rated, Div. 1 + Div. 2) - 1427314831a - 博客园 (cnblogs.com)](https://www.cnblogs.com/1427314831a/p/15048209.html)

像这一题就是根号的做法过不去，最后换了log的才过

具体思路就是将从后往前找的整除分块过程改为从前往后处理贡献的倍增法

复杂度可以从根号优化到调和级数，也就是log

但当中有个问题，枚举i*j时a[j]的值可能还没求出来，考虑记录这种情况，在a[j]求出来后延迟更新

空间复杂度也将会是一个调和级数，但这题空间只给了128MB，也就是还卡空间

写完延迟更新后发现到a[j]时有一定规律，可以按规律直接去跑，不用存那些情况，空间复杂度降为\(O(n)\)

#include<bits/stdc++.h>
using namespace std;
//#define int long long
int a[4000010],b[4000010],c[4000010],mod;
//vector<int>d[4000040];
int main()
{
	int x;
	scanf("%d%d",&x,&mod);
	a[1]=1;b[1]=1,c[1]=0;
	for(int i=2;i<=x;i++)
	{
		a[i]=(a[i]+b[i-1]);
		if(a[i]>=mod)a[i]-=mod;
		for(int j=1;i*j<=x;j++)
		{
			if(j>=i)
			{
				break;
//				d[j].push_back(i*j);
//				d[j].push_back(i*(j+1));
			}
			else
			{
				c[i*j]+=a[j];
				if(c[i*j]>=mod)c[i*j]-=mod; 
				if(i*(j+1)<=x)
				{
					c[i*(j+1)]-=a[j];
					if(c[i*(j+1)]<0)c[i*(j+1)]+=mod;
				}
			}
		}
		c[i]+=c[i-1];
		if(c[i]<0)c[i]+=mod;
		if(c[i]>=mod)c[i]-=mod;
		a[i]=(a[i]+c[i]);
		if(a[i]>=mod)a[i]-=mod;
		b[i]=(b[i-1]+a[i]);
		if(b[i]>=mod)b[i]-=mod;
		for(int j=1;j<=i&&i*j<=x;j++)
		{
			c[j*i]+=a[i];
			if(c[j*i]>=mod)c[j*i]-=mod;
			if((i+1)*j<=x)
			{
				c[(i+1)*j]-=a[i];
				if(c[(i+1)*j]<0)c[(i+1)*j]+=mod;
			}
		}
//		for(int j=0;j<d[i].size();j+=2)
//		{
//			c[d[i][j]]+=a[i];
//			if(c[d[i][j]]>=mod)c[d[i][j]]-=mod;
//			c[d[i][j+1]]-=a[i];
//			if(c[d[i][j+1]]<0)c[d[i][j]]+=mod;
//		}
//		d[i].clear();
//		d[i].shrink_to_fit();
	}
	printf("%d\n",a[x]);
	return 0;
}
/*
10 998244353
*/