找最大正方形。
预处理一个二维前缀和,然后n方找.的位置,把找到的.当做右下坐标,然后O(n)枚举边长k,复杂度O(n^3)
#include<bits/stdc++.h> using namespace std; int A[305][305]; int B[305][305]; int n,m; int main() { int t; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ getchar(); for(int j=1;j<=m;j++){ A[i][j]=(getchar()=='*'?1:0); B[i][j]=A[i][j]+B[i-1][j]+B[i][j-1]-B[i-1][j-1]; } } int ma=0; bool f=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(A[i][j]==0&&((f=1)==1)){ for(int k=ma;k<=min(n,m);k++){ int x=i-k,y=j-k; if(x>0&&y>0){ if(B[i][j]-B[x-1][j]-B[i][y-1]+B[x-1][y-1]==0){ ma=max(k,ma); }else{ break; } } else{ break; } } } } } if(f) cout<<(ma+1)*(ma+1)<<'\n'; else puts("0"); } }
$\sum_{i=1}^{n}\sum_{j=1}^{m}i*j*(n\mod i)*(m\mod j)=\sum_{i=1}^{n}i*(n\mod i)*\sum_{j=1}^{m}j*(m\mod j)$
数论分块,想了半天才想到分块,不然T恤就没了QAQ,取模出锅,WA了N发==,太菜了
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll mod=1e9+7; ll inv2,inv6; ll n,m; ll inv(ll x) { ll ans=1; ll n=mod-2; while(n) { if(n&1) { ans=ans*x%mod; } x=x*x%mod; n>>=1; } return ans; } ll C(ll a,ll b,ll c,ll x) { ll t=(1+b-a+mod)%mod*(2*a*a%mod+2*a*b%mod-a+2*b*b%mod+b+mod)%mod*inv6%mod; ll d=(b+1-a+mod)%mod*(a+b)%mod%mod*inv2%mod; ll ans=(x*d%mod-c*t%mod+mod)%mod; return ans%mod; } ll cal(ll x) { ll ans=0; int i=1; for(i=1; x/i>=100000; i++) { ans=(ans+C(x/(i+1)+1,x/i,i,x))%mod; } ll t=x/i; for(int j=1;j<=t;j++){ ans=(ans+j*(x%j)%mod)%mod; } return ans; } int main() { inv2=inv(2); inv6=inv(6); scanf("%lld%lld",&n,&m); // cout<<cal(n)<<'\n'; // cout<<cal(m)<<'\n'; cout<<cal(n)*cal(m)%mod<<'\n'; /* ll ans=0; for(int i=1;i<=n;i++){ ans=(ans+i*(n%i))%mod; } cout<<ans<<'\n'; ans=0; for(int i=1;i<=m;i++){ ans=(ans+i*(m%i))%mod; } cout<<ans<<'\n'; ans=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ ans=(ans+i*j%mod*(n%i)%mod*(m%j)%mod)%mod; } } cout<<ans<<'\n';*/ } //2500001 10100101
计数一个N个顶点的带标签图的所有不同的生成树的叶子节点个数的和。
N个结点的带标签图生成树个数为N^(N-2)
考虑去掉任一顶点,假设这个点为叶子结点,这个点跟剩余n-1个点能连n-1条不同的边,然后剩下n-1个点能构成(n-1)^(n-3)棵不同的生成树,再由这个点的任意性,就是n*(n-1)^(n-2)
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll mod=998244353; ll N; ll A[1000005]; ll qp(ll x,ll n) { ll ans=1; // ll n=mod-2; while(n) { if(n&1) { ans=ans*x%mod; } x=x*x%mod; n>>=1; } return ans; } int main() { scanf("%lld",&N); //cout<<N<<'\n'; cout<<N*qp(N-1,N-2)%mod<<'\n'; }