有个朴素的暴力,枚举每一个子矩形,复杂度 \(O(n^{2}m^{2})\),观察数据范围,n很小,考虑枚举行,对于 \(m\) 用 \(two\;pointers\) 来维护。
先预处理出每一列的前缀和,然后枚举行,对于列,用个双指针,把 \([l,r]\) 这一段区间卡出来,答案每回累加合法的区间长度即可。
复杂度 \(O(n^{2}m)\)
#include<cmath> #include<cstdio> #define MAX 50100 #define re register #define int long long namespace OMA { char ch[MAX]; int n,m,l,r,tot[MAX]; int ans,sum[33][MAX]; struct stream { template<typename type>inline stream &operator >>(type &s) { int w=1; s=0; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')w=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*=w,*this; } }cin; signed main() { //freopen("node.in","r",stdin); cin >> n >> m; for(re int i=1; i<=n; i++) { scanf("%s",ch+1); for(re int j=1; j<=m; j++) { sum[i][j] = sum[i-1][j]+(ch[j]=='1'); } } cin >> l >> r; for(re int i=1; i<=n; i++) { for(re int j=i; j<=n; j++) { int lp = 0,rp = 0; for(re int k=1; k<=m; k++) { //printf("i=%lld j=%lld k=%lld ",i,j,k); tot[k] = tot[k-1]+sum[j][k]-sum[i-1][k]; //printf("tot[%lld]=%lld\n",k,tot[k]); while(tot[k]-tot[lp]>r&&lp+1<k) { lp++; } while(tot[k]-tot[rp+1]>=l&&rp+1<k) { rp++; } if(tot[k]-tot[rp]>=l) { ans += rp-lp+1; } } } } printf("%lld\n",ans); return 0; } } signed main() { return (OMA::main(),0); }
好了,现在你已经知道转换后的题意,问题在于如何求解 \(cnt\) 数组和答案。
对于每一行,我们都开一个桶记录 \(a\) 出现的次数。
然后枚举每一行,再从1枚举到最大值,再枚举当前枚举的数的倍数,加上上边说的桶即可 建议看code
这样得到的 \(cnt_{i,j}\) 表示第i行有多少个数为j的倍数,每一行求和就是总的,而我们要的是j,所以考虑一波容斥,即减去j的其他倍数即可,这样的话就要倒序枚举最大值。
复杂度 \(O(n(m+\max\{a\}\ln\max\{a\}))\) 。
#include<cstdio> #define MAX 100010 #define re register #define int long long const int N = 22; namespace OMA { int n,m,xam,ans; int a[N][MAX]; int buc[N][MAX]; int cnt[N][MAX],sum[MAX]; const int p = 1e9+7; struct stream { template<typename type>inline stream &operator >> (type &s) { int w=1; s=0; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')w=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*=w,*this; } }cin; inline int max(int a,int b) { return a>b?a:b; } signed main() { cin >> n >> m; for(re int i=1; i<=n; i++) { for(re int j=1; j<=m; j++) { cin >> a[i][j]; xam = max(xam,a[i][j]); buc[i][a[i][j]]++; } } for(re int i=1; i<=n; i++) { for(re int j=1; j<=xam; j++) { for(re int k=1; j*k<=xam; k++) { cnt[i][j] += buc[i][j*k]; } } } /*for(re int i=1; i<=n; i++) { for(re int j=1; j<=xam; j++) { printf("%lld ",cnt[i][j]); } printf("\n"); }*/ for(re int j=xam; j; j--) { sum[j] = 1; for(re int i=1; i<=n; i++) { (sum[j] *= cnt[i][j]+1) %= p; } sum[j] -= 1; if(!sum[j]) { continue ; } for(re int k=2; k*j<=xam; k++) { sum[j] -= sum[k*j]; } (ans += j*sum[j]) %= p; } printf("%lld\n",(ans+p)%p); return 0; } } signed main() { return OMA::main(); }
点分治,不会,爬了