A. a
显然本题应该是\(n*m\)做法,然而我带了个树状数组的\(log\),卡了卡过了..
正解应该是枚举左上端点,然后考虑维护两个单调指针..
我们发现随着右下端点高度的下移,那么\(l\)和\(r\)作为边界的指针也会单调向左移动..
于是\(O(n*m)\)便可做了..
A_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS {
#define ll int
#define ull unsigend ll
#define re register ll
#define lf double
#define lbt(x) (x&(-x))
#define mp(x,y) make_pair(x,y)
#define lb lower_bound
#define ub upper_bound
#define File(x,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout)
#define Fill(x,y) memset(x,y,sizeof x)
#define Copy(x,y) memset(x,y,sizeof x)
inline ll read() {
ll ss=0; bool cit=1; char ch;
while(!isdigit(ch=getchar())) if(ch==‘-‘) cit=0;
while(isdigit(ch)) ss=(ss<<3)+(ss<<1)+(ch^48),ch=getchar();
return cit?ss:-ss;
}
} using namespace BSS;
const ll N=35,M=5e4+51;
ll m,n,l,r,flag;
long long int ans;
char s[M];
ll c[N*M],f[N*M];
ll g[N][M],pre[N][M],sum[M*N];
inline ll query(ll x){
ll res=0;
if(x<0) return 0;
while(x) res+=c[x],x-=lbt(x);
return res+c[0];
}
inline void update(ll x,ll num){
if(x==0) c[x]+=num;
else while(x<=pre[n][m]+2) c[x]+=num,x+=lbt(x);
return ;
}
signed main(){
n=read(),m=read();
flag=1;
for(re i=1;i<=n;++i){
scanf("%s",s+1);
for(re j=1;j<=m;++j)
pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+s[j]-‘0‘,
flag&=(s[j]==‘1‘);
}
l=read(),r=read();
if(flag){
for(re i=1;i<=n;i++){
for(re j=1;j<=m;j++){
if(i*j>r) break;
if(i*j>=l and i*j<=r) ans+=1ll*(n-i+1)*(m-j+1);
}
}
printf("%lld",ans);
return 0;
}
if(l==0 and r==n*m){
for(re i=1;i<=n;i++)
for(re j=1;j<=m;j++)
ans+=1ll*(n-i+1)*(m-j+1);
printf("%lld",ans);
return 0;
}
ll temp,cnt;
for(re i=0;i<=n;++i){
for(re j=i+1;j<=n;++j){
cnt=0;
for(re k=0;k<=m;++k){
temp=pre[j][k]-pre[i][k],
ans+=query(temp-l)-query(temp-r-1);
update(temp,1);
}
for(re k=0;k<=pre[n][m];++k) c[k]=0;
}
}
printf("%lld",ans);
return 0;
}
B. b
考场上考虑了一个维护每个质因子的贡献,然而事实上并不单单是质因子..
维护每个因子的贡献,发现会有重复,于是简单的容斥原理减去即可.
B_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS {
#define ll long long int
#define ull unsigend ll
#define re register ll
#define lf double
#define mp(x,y) make_pair(x,y)
#define lb lower_bound
#define ub upper_bound
#define File(x,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout)
#define Fill(x,y) memset(x,y,sizeof x)
#define Copy(x,y) memset(x,y,sizeof x)
inline ll read() {
ll ss=0; bool cit=1; char ch;
while(!isdigit(ch=getchar())) if(ch==‘-‘) cit=0;
while(isdigit(ch)) ss=(ss<<3)+(ss<<1)+(ch^48),ch=getchar();
return cit?ss:-ss;
}
} using namespace BSS;
const ll N=25,M=1e5+51;
const ll mod=1e9+7;
ll n,m,maxn,res;
ll ans[M];
ll val[N][M],cnt[N][M],bkt[N][M];
signed main(){
n=read(); m=read();
ll temp=0;
for(re i=1;i<=n;i++)
for(re j=1;j<=m;j++)
temp=read(),maxn=max(maxn,temp),bkt[i][temp]++;
for(re i=1;i<=n;i++){
for(re j=1;j<=maxn;j++)
for(re k=1;k*j<=maxn;k++)
(cnt[i][j]+=bkt[i][k*j])%mod;
}
/* for(re i=1;i<=n;i++){
for(re j=1;j<=maxn;j++)
cout<<cnt[i][j]<<" ";
cout<<‘\n‘;
}
*/ for(re i=maxn;i>=1;i--){
ans[i]=1;
for(re j=1;j<=n;j++) ans[i]=(ans[i]*(cnt[j][i]+1))%mod;
--ans[i];
for(re j=2;j*i<=maxn;j++) ans[i]=(ans[i]-ans[j*i]+mod)%mod;
(res+=ans[i]*i)%=mod;
}
printf("%lld",res);
return 0;
}
C.c
点分治.