[unknown source] 整数拆分

一、题目

题目描述

定义一个整数拆分序列 (a) 的权值为：

[sum_{i=1}^nsum_{j=1}^{i-1}gcd(a_i,a_j) ]

求对于一个整数 (n) 所有整数拆分序列的权值和模 (1e9+7) 的值，有 (m) 个数不能选。

数据范围

(n,mleq2000)，多组数据

二、解法

法一

见到 (gcd) 就用莫比乌斯反演，问题变成了求 (i) 倍数有 (x) 个的整数拆分个数。

暴力完全背包是 (O(n^3log n)) 的，瓶颈在于加入那些贡献为 (0) 的数，所以可以做一个退背包，时间复杂度 (O(n^2log^2n))，这种做法我讲得比较简略因为他是没有前途的（主要是告诉你完全背包也是可以退的）

法二

正解是算贡献（这么强的东西怎么我学不会啊！）

具体来说我们统计每对 ((a_i,a_j)) 的贡献，首先要算一个 (f[i]) 表示去掉不能选的数后 (i) 的整数拆分个数，这个东西暴力算是 (O(n^2)) 的。

然后考虑对于一个拆分序列统计值 (x) 和值 (y) 之间的贡献，设这个拆分序列的 (x) 数量是 (a)，(y) 的数量是 (b)，那么我们肯定要让 (gcd(x,y)) 被统计 (a imes b) 次，但是在真实的计算中我们是不知道 (a,b) 的，只能尝试用 (f) 去表示它，我们枚举 (i,j) 表示 (x) 钦定选 (i) 个，(y) 钦定选 (j) 个，那么我们要在 (iin[1,a],jin[1,b]) 的时候统计一次就可以了，所以贡献算出来是这样的：

稍微解释一下这个钦定，其实它是一个很重要的概念，就表示强制选某些另一些乱选的情况

[sum_{x,y,i,j}gcd(x,y) imes f(n-ix-iy) ]

算贡献的魅力就在于：就算你不知道一些东西，但是他依然是可以统计的

这个东西肯定不能暴力算，有一个比较小清新的优化，设 (t=ix)，求出 (c[t][y]) 表示 (sum f(n-t-jy))，根据调和级数求和的理论不难发现求出这个东西是 (O(n^2log n)) 的，然后暴力枚举 (x,y) 和 (x) 的所有倍数，同样是调和级数的 (O(n^2log n))

白嫖了一个好看的代码：

#include<bits/stdc++.h>
#define maxn 2005
using namespace std;
const int mod = 1e9+7;
int n,m,ans,a[maxn],g[maxn][maxn],f[maxn],c[maxn][maxn];
bool ban[maxn];
inline int add(int x,int y){return (x+=y)>=mod?x-mod:x;}
int main()
{
	freopen("zscf.in","r",stdin);
	freopen("zscf.out","w",stdout);
	for(int i=1;i<=2000;i++)
		for(int j=i;j<=2000;j++)
			g[i][j]=g[j][i]=__gcd(i,j);
	while(~scanf("%d%d",&n,&m)){
		memset(ban,0,n+1),ans=0;
		for(int i=1,x;i<=m;i++) scanf("%d",&x),ban[x]=1;
		memset(f,0,(n+1)<<2),f[0]=1;
		for(int i=1;i<=n;i++) if(!ban[i])
			for(int j=i;j<=n;j++)
				f[j]=add(f[j],f[j-i]);
		for(int j=1;j<=n;j++) if(!ban[j])
			for(int i=n;i>=1;i--)
				if(i+j<=n) c[i][j]=add(c[i+j][j],f[n-i-j]);
				else c[i][j]=0;
		for(int i=1;i<=n;i++) if(!ban[i]){
			int cnt=0;
			for(int x=1,s=i;s<=n;s+=i,x++){
				if(s+i<=n) cnt=add(cnt,1ll*x*f[n-s-i]%mod);
				for(int j=1;j<i;j++) if(!ban[j])
					ans=add(ans,1ll*g[i][j]*c[s][j]%mod);
			}
			ans=add(ans,1ll*cnt*i%mod);
		}
		printf("%d
",ans);
	}
}