开场几十分钟后才开始打的，实验室居然锁门了。。。
左上、右下角为（1,1）、（x,y）的矩阵的大小，dp处理
然后一个裸的二分答案
(1,1) (x,y) (x-k,y-k) 三个点
sum=
update:
题解说O(Tn^3)就是不严谨了。
20*300^3=540000000
这样都说能过！！！
如此接近1秒可以跑的数据量，
有时要考虑常数的大小，是否没跑满的情况！然而没有提及。
我的第二个代码：
n^2+(n-1)^2+...+1^1 = 1/6 * n*(n+1)*(2n+1)
相当于/3，实际是180901000，已经是极为接近了。
估计有些n^3的写法，也有这样的时间复杂度可以除以一个系数的情况。
而实际上呢，
有数据可以让它跑满吗？
可以的，如
然而出题人有这种闲情逸致弄这样的极限数据吗？
我不认为。。。
就像有些邀请赛，如2019南昌邀请赛。。。
（然而经过常数优化后，633ms过了）
搞个快读，多交几次，估计就能过去了。
有时也要考虑一下这种类型的情况。。。
另外一个更巧妙的O(n^3)防被卡方法：
右下端点按照可以制造的最大矩阵的大小，从大到小进行处理
避免全为'*'和全为'.'两个极端数据的卡
几十ms
code1:
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 #define ll long long10 11 const double eps=1e-8;12 const ll inf=1e9;13 const ll mod=1e9+7;14 const int maxn=3e2+10;15 16 char str[maxn][maxn];17 int f[maxn][maxn];18 19 int main()20 {21 int t,n,m,l,r,mid,i,j;22 bool vis;23 scanf("%d",&t);24 while (t--)25 {26 scanf("%d%d",&n,&m);27 for (i=1;i<=n;i++)28 scanf("%s",str[i]+1);29 30 for (i=1;i<=n;i++)31 for (j=1;j<=m;j++)32 f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+(str[i][j]=='.');33 34 l=1,r=min(n,m);35 while (l<=r)36 {37 mid=(l+r)>>1;38 vis=0;39 40 for (i=mid;i<=n;i++)41 for (j=mid;j<=m;j++)42 if (f[i][j]-f[i-mid][j]-f[i][j-mid]+f[i-mid][j-mid]==mid*mid)43 vis=1; ///写成函数形成，遇到则退出true，这样会快一点；但是写起来不方便44 if (vis)45 l=mid+1;46 else47 r=mid-1;48 }49 printf("%d\n",r*r);50 }51 return 0;52 }
code2:
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 #define ll long long10 11 const double eps=1e-8;12 const ll inf=1e9;13 const ll mod=1e9+7;14 const int maxn=3e2+10;15 16 char str[maxn][maxn];17 int f[maxn][maxn];18 19 int main()20 {21 int t,n,m,i,j,k,l,r,g;22 scanf("%d",&t);23 while (t--)24 {25 scanf("%d%d",&n,&m);26 for (i=1;i<=n;i++)27 scanf("%s",str[i]+1);28 29 for (i=1;i<=n;i++)30 for (j=1;j<=m;j++)31 f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+(str[i][j]=='.');32 33 /**34 避免全为'*'和全为'.'两个极端数据的卡35 **/36 37 r=0;38 ///from large to small39 for (i=n+m;i>r;i--)40 {41 for (j=max(1,i-m);j<=n;j++)42 {43 k=i-j;44 g=min(j,k);45 for (l=r+1;l<=g;l++) ///r+1来自乐逍大佬提醒46 if (f[j][k]-f[j-l][k]-f[j][k-l]+f[j-l][k-l]!=l*l)47 break;48 if (l!=r+1)49 r=l-1;50 }51 }52 printf("%d\n",r*r);53 }54 return 0;55 }56 /*57 158 2 359 ...60 .**61 62 3 463 ****64 ****65 ****66 67 3 468 ....69 ....70 ....71 72 4 473 ....74 ....75 ....76 ....77 */
n,m为独立的两部分，相乘即可
接下来是整除分块，对于同一块，余数是一个等差数列
update:
我只是找到了规律，
应该培养推公式的能力。。。
n%i 的数学式子
gcd 的数学式子
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 #define ll long long 10 11 const double eps=1e-8; 12 const ll inf=1e9; 13 const ll mod=1e9+7; 14 const int maxn=1e5+10; 15 16 ///sum(sum(i*j*(n mod i)(m mod j)) mod 1e9+7 17 ///1e9 18 19 int maxv=1e5; 20 21 //int zhi[maxn]; 22 bool vis[maxn]; 23 24 ll work(ll n) 25 { 26 ll l,r,sum=0,a0,b0,q,g,xx,yy,zz; 27 for (l=1;l<=n;l=r+1) 28 { 29 r=n/(n/l); 30 if (l==r) 31 sum+=n%l*l; 32 else 33 { 34 ///a0=l,b0,q,g 35 a0=l; 36 b0=n%l; 37 q=n/l; 38 g=r-l+1; 39 40 ///0^2+1^2+... 41 (sum+=a0*b0%mod*g)%=mod; 42 if (g&1) 43 (sum+=b0*g%mod*((g-1)/2))%=mod; 44 else 45 (sum+=b0*(g/2)%mod*(g-1))%=mod; 46 if (g&1) 47 (sum-=a0*q%mod*g%mod*((g-1)/2))%=mod; 48 else 49 (sum-=a0*q%mod*(g/2)%mod*(g-1))%=mod; 50 51 xx=g-1; 52 yy=g; 53 zz=2*g-1; 54 if (xx%2==0) 55 xx/=2; 56 else if (yy%2==0) 57 yy/=2; 58 else 59 zz/=2; 60 if (xx%3==0) 61 xx/=3; 62 else if (yy%3==0) 63 yy/=3; 64 else 65 zz/=3; 66 (sum-=q*xx%mod*yy%mod*zz)%=mod; 67 // q*(g-1)*g*(2*g-1)/6 68 ///sum+=a0*b0*g + b0*g*(g-1)/2 - a0*q*g*(g-1)/2 - q*(g-1)*g*(2*g-1)/6; 69 70 // sum+=a0*g-q*g*(g-1)/2; 71 } 72 // printf("%lld %lld\n",l,r); 73 } 74 return sum; 75 } 76 77 int main() 78 { 79 /* 80 ///n 最小的质因数 81 for (i=2;i<=maxv;i++) 82 { 83 if (!vis[i]) 84 { 85 zhi[++cnt_zhi]=i; 86 for (j) 87 } 88 } 89 */ 90 91 ll n,m,i; 92 ///two parts 93 scanf("%lld%lld",&n,&m); 94 printf("%lld",(work(n)*work(m)%mod+mod)%mod); 95 return 0; 96 } 97 /* 98 1 1 99 2 2100 3 3101 4 4102 5 5103 6 6104 7 7105 1000000000 1000000000106 */
菜鸡不会推公式，只能找规律
打表
看这：
http://blog.csdn.net/morejarphone/article/details/50677172
https://www.cnblogs.com/dirge/p/5503289.html
无根树 & prufer
n^(n-2)
update:
我觉得没多少人能按照题解的方法写出来。。。
我感觉更多的是xxx，甚至是yyy。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 #define ll long long10 #include 11 12 const double eps=1e-8;13 const ll inf=1e9;14 const ll mod=1e9+7;15 const int maxn=15;16 17 int n,a[maxn],hap[maxn],link[maxn],siz_n;18 ll sum=0;19 set se;20 21 void judge(int step)22 {23 int x,y;24 if (step==n-1)25 {26 x=*se.begin();27 se.erase(se.begin());28 y=*se.begin();29 se.erase(se.begin());30 link[x]++,link[y]++;31 for (x=1;x<=n;x++)32 if (link[x]==1)33 sum++;34 return;35 }36 x=*se.begin();37 se.erase(se.begin());38 y=a[step];39 link[x]++,link[y]++;40 hap[y]--;41 if (hap[y]==0)42 se.insert(y);43 judge(step+1);44 }45 46 void work(int step)47 {48 int i;49 if (step==n-1)50 {51 se.clear();52 memset(hap,0,siz_n);53 memset(link,0,siz_n);54 for (i=1;i<=n;i++)55 hap[a[i]]++;56 for (i=1;i<=n;i++)57 if (hap[i]==0)58 se.insert(i);59 judge(1);60 return;61 }62 for (i=1;i<=n;i++)63 {64 a[step]=i;65 work(step+1);66 }67 }68 69 int main()70 {71 for (n=2;n<=10;n++)72 {73 siz_n=4*(n+1);74 sum=0;75 work(1);76 printf("n=%d sum=%lld\n",n,sum);77 }78 return 0;79 }80 /*81 n=2 sum=282 n=3 sum=683 n=4 sum=3684 n=5 sum=32085 n=6 sum=375086 n=7 sum=5443287 n=8 sum=94119288 n=9 sum=1887436889 90 n * (n-1)^(n-2)91 */
代码
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 #define ll long long10 11 const double eps=1e-8;12 const ll inf=1e9;13 const ll mod=998244353;14 const int maxn=1e5+10;15 16 ll mul(ll a,ll b)17 {18 ll y=1;19 while (b)20 {21 if (b&1)22 y=y*a%mod;23 a=a*a%mod;24 b>>=1;25 }26 return y;27 }28 29 int main()30 {31 ll n;32 scanf("%lld",&n);33 if (n==1)34 {35 printf("1");36 return 0;37 }38 39 printf("%lld",n*mul(n-1,n-2)%mod);40 return 0;41 }42 /*43 n=2 sum=244 n=3 sum=645 n=4 sum=3646 n=5 sum=32047 n=6 sum=375048 n=7 sum=5443249 n=8 sum=94119250 n=9 sum=1887436851 52 n * (n-1)^(n-2)53 */
来自群里的大佬解答
证明：
1.不同的 大小为n-1的两个无根树，加上一个无根树后，还是无根树。
2.在一个无根树的两个不同的点，加上这个点，唯一与这个点相连的点的度数加一，与其它无根树不一样了。
引用另外的大佬一句总结
