题面：https://www.cnblogs.com/Juve/articles/11428730.html
chinese：
考虑$sumlimits_{i=0}^{n*m}i*f_i$的意义:所有方案中炼字的个数之和。
统计答案时可以考虑[1,k]每个字对答案的贡献,即每个字在多少种方案中成为炼字。
在方格的一个确定位置(x,y),字符i对答案的贡献((x,y)位置的数是i且i是炼字的方案数)是
$(i-1)^{n-1}*(i-1)^{m-1}*k^{n*m-n-m+1}$。
由于诗作中的所有位置都是等价的,那么最后的答案就是
$n*m*sumlimits_{i=0}^{k}(i-1)^{n-1}*(i-1)^{m-1}*k^{n*m-n-m+1}$。
时间复杂度O(k)。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
const int mod=1e9+7;
int n,m,k,ans=0;
int q_pow(int a,int b,int p){
int res=1;
while(b){
if(b&1) (res*=a)%=mod;
(a*=a)%=mod;
b>>=1;
}
return res%mod;
}
signed main(){
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=1;i<=k;i++)
(ans+=(q_pow(i-1,n-1,mod)*q_pow(i-1,m-1,mod)%mod*q_pow(k,n*m-n-m+1,mod)%mod))%=mod;
(ans*=(n*m%mod))%=mod;
printf("%lld
",ans);
return 0;
}
physics:
数据过水导致$O(qn^2log_2n)$过了
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define MAXN 1005
#define re register
using namespace std;
int n,m,q,ans,l,r,mid,sum[MAXN][MAXN],ansi,ansj,x,y;
char ch[MAXN];
inline int read(){
int a=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9'){
a=(a<<3)+(a<<1)+ch-'0';
ch=getchar();
}
return a;
}
inline bool judge(re int k){
for(re int i=1;i<=n-k+1;i++){
for(re int j=1;j<=m-k+1;j++){
re int res=sum[i+k-1][j+k-1]+sum[i-1][j-1]-sum[i+k-1][j-1]-sum[i-1][j+k-1];
if(res==k*k){
ansi=i,ansj=j;
return 1;
}
}
}
return 0;
}
signed main(){
//freopen("physics4.in","r",stdin);
n=read(),m=read(),q=read();
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]+sum[i][j-1]-sum[i-1][j-1];
if(ch[j]=='-') continue;
sum[i][j]++;
}
}
ans=min(n,m),ansi=0,ansj=0;
while(q--){
x=read(),y=read();
for(re int i=x;i<=n;i++){
for(re int j=y;j<=m;j++)
sum[i][j]--;
}
if(ans!=min(n,m)&&(x<ansi||x>ansi+ans-1||y<ansj||y>ansj+ans-1)){
printf("%d
",ans);
continue;
}
l=0,r=ans,ans=0;
while(l<=r){
mid=(l+r)>>1;
if(judge(mid)){
ans=mid;
l=mid+1;
}
else r=mid-1;
}
printf("%d
",ans);
}
return 0;
}
正解：
典型的时光倒流,先将所有待修改的正电荷都修改为负电荷,然后倒序考虑所有修改操作。
考虑如何在较优复杂度内计算最后一次修改后的答案(经典问题):
upi,j 表示 (i, j) 向上延伸的正电荷的最长长度。
downi,j 表示 (i, j) 向下延伸的正电荷的最长长度。
可以通过单调栈求出 lefti,j 表示 (i, j) 左面第一个小于 upi,j 的位
置, righti,j 表示 (i, j) 右面第一个小于 upi,j 的位置。
那么问题的答案就是max{min(upi,j,righti,j−lefti,j+1)} 。
时间复杂度 O(n2)
对于多次修改操作:
倒序考虑所有操作,如果答案增加,那么一定是由于当前(x, y) 位置负电荷变正电荷造成的。每次修改操作只会影响一列的 up, down ,可以暴力修改。考虑当前负电荷变正电荷后是否存在边长为 k 的正方形,那么问题就转化为是否存在min{upx,[i,i+k−1]}+min{downx,[i,i+k−1]}≥k 。求长度固定的区间的最小值,这就转化成单调队列的经典问题(滑动的窗口)。每次负电荷变正电荷后,可以二分求出由于此次修改造成的更优答案。
时间复杂度$O(n^2+qnlogn)$。
chemistry:
留坑