洛谷 P6189 - [NOI Online #1 入门组]跑步（根号分治+背包）

题意：

求有多少个数列 \(x\) 满足：

\(\sum x_i=n\)
\(x_i\geq x_{i+1}\)

答案对 \(p\) 取模。

。。。你确定这叫“入门”组？

一眼完全背包问题，然而 \(n^2\) 是根本过不了的，于是我便在那里打表找规律，结果毛用也没有（

考虑根号分治，令 \(m=\lfloor\sqrt{n}\rfloor\)。

对于 \(i\leq m\) 跑一遍完全背包。

对于 \(i>m\)，不难发现我们顶多会选 \(m\) 个这样的 \(i\)，所以我们采取另一种 \(dp\) 状态。

我们记 \(g_{i,j}\) 为选择了 \(i\) 个这样的 \(i\)，它们的和为 \(j\) 的方案数。

那么有转移方程 \(g_{i,j}=g_{i-1,j-m-1}+g_{i,j-i}\)。

稍微解释一下这个 \(dp\) 方程，\(g_{i-1,j-m-1}\) 表示在序列末尾新增添一个 \(m+1\)，\(g_{i,j-i}\) 表示将序列中所有数 \(+1\)，由于我们得到的序列是单调递减的，所以一种方案一定恰好对于一种操作序列。

最后是计算答案，枚举 \(\leq m\) 的数和是多少，以及选择了多少个 \(>m\) 的数，可以在 \(\mathcal O(n\sqrt{n})\) 的时间内计算出答案。

总时间复杂度 \(\mathcal O(n\sqrt{n})\)。

感觉有点像 atcoder 风格的题。

#include <bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define fz(i,a,b) for(int i=a;i<=b;i++)

#define fd(i,a,b) for(int i=a;i>=b;i--)

#define ffe(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)

#define fill0(a) memset(a,0,sizeof(a))

#define fill1(a) memset(a,-1,sizeof(a))

#define fillbig(a) memset(a,63,sizeof(a))

#define pb push_back

#define ppb pop_back

#define mp make_pair

typedef pair<int,int> pii;

typedef long long ll;

const int MAXN=1e5+5;

const int SQRT=320;

int n,m,p;

int dp[MAXN],f[SQRT][MAXN];

int main(){

	scanf("%d%d",&n,&p);m=(int)(sqrt(n));

	dp[0]=1;

	for(int i=1;i<=m;i++){

		for(int j=i;j<=n;j++) dp[j]=(dp[j]+dp[j-i])%p;

	}

	f[0][0]=1;

	for(int i=1;i<=m;i++){

		for(int j=1;j<=n;j++){

			if(j>=i) f[i][j]=f[i][j-i];

			if(j>=m+1) f[i][j]=(f[i][j]+f[i-1][j-m-1])%p;

		}

	}

	int ans=0;

	for(int i=0;i<=n;i++) for(int j=0;j<=m;j++)

		ans=(ans+1ll*dp[i]*f[j][n-i])%p;

	printf("%d\n",ans);

	return 0;

}

巴特西

洛谷 P6189 - [NOI Online #1 入门组]跑步（根号分治+背包）

最新文章

热门文章