T1 a

这道题，考试的时候我一直认为要用线段树，可是自己不会用，还不断的hack掉自己的线段树思路，最后没办法只能打了一个\(m^2*n^2\)的暴力，加上一些特殊性质，本来能拿50分，结果自己没有考虑周到，在测试点分治的时候没弄好，把那个二级数据直接略过了，导致只拿了30分。而正解的思路就是在暴力的基础上优化掉一个m,达到 \(n^2*m\),具体做法就是我们只枚举左上角的顶点，因为满足要求的右下角顶点必定在一个单调递增的区间中，所以满足决策单调性，可以使用二分在log的时间内算出合法的区间数，但是需要加上一些剪枝优化，具体实现见代码：

AC_code


#include<bits/stdc++.h>
#define re register int
#define ii inline int
#define iv inline void
using namespace std;
const int N=5e4+10;
const int INF=1e7+10;
int n,m;
long long ans;
char s[35][N];
int sum[35][N];
ii read()
{
	int x=0;
	bool f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
			f=0;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f?x:(-x);
}
signed main()
{
	int l,r;
	n=read();
	m=read();
	for(re i=1;i<=n;i++)
		scanf("%s",s[i]+1);
	l=read();
	r=read();
	for(re i=1;i<=n;i++)
	{
		for(re j=1;j<=m;j++)
		{
			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
			if(s[i][j]=='1')
				sum[i][j]+=1;
		}
	}
	int L,R,nl,nr;
	for(re i=1;i<=n;i++)
	{
		for(re k=i;k<=n;k++)
		{
		  for(re j=1;j<=m;j++)
		  {
				if(sum[k][m]-sum[i-1][m]-sum[k][j-1]+sum[i-1][j-1]<l || sum[k][j]-sum[i-1][j]-sum[k][j-1]+sum[i-1][j-1] >r) continue;
				L=j,R=m,nl=m+1,nr=m+1;
				if(sum[k][j]-sum[i-1][j]-sum[k][j-1]+sum[i-1][j-1]>=l) nl=j; 
				else 
					while(L<=R)
					{
						int mid=(L+R)>>1;
						if(sum[k][mid]-sum[i-1][mid]-sum[k][j-1]+sum[i-1][j-1]>=l)
						{
							nl=mid;
							R=mid-1;
						}
						else
							L=mid+1;
					}
				L=j,R=m;
				if(sum[k][m]-sum[i-1][m]-sum[k][j-1]+sum[i-1][j-1]<=r) nr=m;
				else
					while(L<=R)
					{
						int mid=(L+R)>>1;
						if(sum[k][mid]-sum[i-1][mid]-sum[k][j-1]+sum[i-1][j-1]<=r)
						{
							nr=mid;
							L=mid+1;
						}
						else
							R=mid-1;
					}
				ans+=nr-nl+1;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

T2 b

思路：这里记 a 的最大值为 x。
将问题转化为“对 \(i∈[1,1e5]\),求多少种选择方案使得 \(gcd=i\)。
继续转化为“对 \(i∈[1,1e5]\),求多少种选择方案使得 \(i|gcd\),
等价于对\(i∈[1,1e5]\),求多少种选择方案使得选的所有数均为 i 的倍数
我们预处理出\(cnt_{i,j}\)表示第 i 行中有多少个数是 j 的倍数，
那么答案就是\(∏\limits_{i=1}^n = (cnt_{i,j} + 1) − 1\)
最后注意去重，所以我们要倒序枚举，每次去掉出现过的当前数的倍数的答案，具体实现见代码：

AC_code


#include<bits/stdc++.h>
#define int long long
#define re register int
#define ii inline int
#define iv inline void
#define lc (rt<<1)
#define rc (rt<<1|1)
#define mid ((l+r)>>1)
using namespace std;
const int mo=1e9+7;
const int N=1e5+10;
int n,m,maxx,ans;
int a[30][N];
int to[30][N],cnt[30][N];
int an[N];
ii read()
{
	int x=0;
	bool f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
			f=0;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return f?x:(-x);
}
signed main()
{
	n=read();
	m=read();
	for(re i=1;i<=n;i++)
	{
		for(re j=1;j<=m;j++)
		{
			a[i][j]=read();
			maxx=max(maxx,a[i][j]);
			to[i][a[i][j]]++;
		}
	}
	for(re i=1;i<=n;i++)
	{
		for(re j=1;j<=maxx;j++)
			for(re k=1;k*j<=maxx;k++)
				cnt[i][j]+=to[i][j*k];
	}
	for(re i=maxx;i;i--)
	{
		an[i]=1;
		for(re j=1;j<=n;j++)
			an[i]=(an[i]%mo*(cnt[j][i]+1))%mo;
		an[i]--;
		for(re j=2;j*i<=maxx;j++)
			an[i]-=an[j*i];
		ans=(ans%mo+an[i]%mo*i%mo+mo)%mo;
	}		
	printf("%lld\n",(ans%mo+mo)%mo);
	return 0;
}