题目

戳这里

( ext{T}_1: ext{ LYK loves games})

咕咕咕...

( ext{T}_2: ext{ LYK loves matrix})

解法

首先容易发现，需要构造出 (a) 数组满足（默认同余时模数为 ( ext{mod})）

[c[i+1][j]-c[i][j]equiv a[i+1]-a[i] ]

我们不需要刻意使 (b) 数组满足类似的条件，为什么会在后文讲。

令 (c[i+1][j]-c[i][j]=d[j])，则有

[d[1]equiv d[2]equiv...equiv a[i+1]-a[i] ]

等价于 (d[j]-d[1]equiv 0 (jin (1,m])) 且 (a[i+1]-a[i]equiv d[1])。

考虑第一个条件，令

[ ext{mod}=gcd_{j=2}^m (d[j]-d[1]) ]

注意如果 ( ext{mod}) 小于等于 (c) 数组的 (max) 是不合法的，初始化可以将其设为 (0)。

接着我们还有一个结论：假设构造出一组 (a,b) 满足条件，我们可以将 (a) 数组每个元素加上 (k)，(b) 数组每个元素减去 (k)，这样仍然满足。

所以令 (a[1]=0,b[i]=c[1][i])，如果有解就一定能构造出来。

最后可由第二个条件推出 (a) 数组：

[a[i+1]equiv a[i]+c[i+1][1]-c[i][1] ]

现在讲讲为什么不需要刻意使 (b) 数组满足类似的条件。由构造方法我们已经满足 (c) 数组的第一行，且行之间的差满足条件且对于那一行的每一列都相同，显然加上同样的数，列之间的差不会改变。

代码

咕咕咕...

( ext{T}_3: ext{ LYK loves })整数拆分

解法

~~为什么今天数据范围都这么小啊喂~~

考虑 (nle 2000)，我们可以枚举数字 (i,j)，然后计算 (gcd(i,j)) 的系数。

但是，(gcd(i,j)) 的系数被分割成了很多个子问题：对于每个拆分方式，若 (i,j) 分别出现了 (x,y) 次，那么在这个拆分方式中 (gcd(i,j)) 的系数为 (x imes y)。若很多个拆分方式存在 (i,j)，我们需要将每个拆分方式中 (gcd(i,j)) 的系数相加。

显然不能直接枚举拆分方式计算，~~不然和暴力有什么区别~~。于是我们自然地想到求解满足 (i,j) 分别出现了 (x,y) 次的拆分方式的种类数。

容易发现这玩意没法做。但是，求解满足 (i,j) 分别出现了至少 (x,y) 次的拆分方式的种类数很好做。设 (f_i) 为拆分 (i) 的种类数，这个可以直接背包。容易发现 (f_{n-ix-jy}) 就是我们所需。

如何计算？容易发现 (i,j) 分别出现了至少 (x,y) 次的拆分方式会在枚举 (ain [1,x],bin [1,y])（ (i,j) 分别出现了 (a,b) 次）时被 (f) 数组统计。

你会惊喜地发现，被统计的次数不正是 (x imes y) 吗？

于是可以得出答案的柿子：

[ ext{Ans}=sum_{i,j,x,y}gcd(i,j) imes f_{n-ix-jy} ]

根据调和级数求和时间复杂度 (mathcal O(n^2log^2n))。~~好耶！~~

考虑固定 (i,j,x)，此时我们可以求 (f_{n-ix-y}+f_{n-ix-2y}+...+f_{n-ix-jy})（其中 (n-ix-jy<0)），这样就可以省掉一个 (log)，时间复杂度 (mathcal O(n^2log n))。

代码

嫖了学长 ( ext{Master. Yi}) 的代码。

#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);
	}
}