首先看问题一（算最小周长），并没有用题解的神奇结论，而是直接整除分块枚举\((n-1)/x\)，取对应的最小x，在\(\sqrt n\)种可能内取最优的（能暴力算为什么要考虑结论呢）然而最后这部分被卡常了，，，整除分块换成枚举x才过，先总结一下这部分的常数问题：
对于整除分块，如果对于一个x，需要知道能得到\(n/y=x\)的y的区间，就需要正常写；如果只需要左端点，那么根号范围内枚举较小数即可，\(n/i\)就是左端点，可以节省一些常数（大概是少了一个除法吧）。
需要左右端点
int m=n-1,t=0,mn=n+n+2,ans=0;
for(int i=1;i<=n;){
int x=m/i,j;
if(!x) j=n;
else j=m/x;
if(i+x+1>mn){
i=j+1;
continue;
}
node u=(node){i,i+x+1};
mn=u.s;
p[++t]=u;
i=j+1;
}
只需要左端点
int m=(int)sqrt(n)+1,t=0,mn=n+n+2,ans=0;
for(int i=1;i<=m;i++){
int x=(n-1)/i+1;
//此题x和n/x是对称等价的，一般的题还要work(n/i)
if(x<i) continue;
if(i+x>mn) continue;
mn=i+x;
p[++t]=(node){i,i+x};
}
(小问题搞了半天，这就是不想动脑的代价)
回到正题，考虑方案数，原本naive了以为每列的都填满或者只有一个为空，后来发现只要是一个凸多边形即可，然后感觉是个dp，但没想清楚就结束了。
对于这个凸多边形，直接dp有点麻烦；但发现本质上是在两个维度上是凸的，而凸本身又可以分为两个单调的部分，而这些问题都是相似的，即将凸多边形分为四个阶梯状；为了避免对凸多边形划分不同的重复计数，考虑空白的部分，就是四个角的阶梯状。
考虑如果已知四个角分别的面积，在保证它们不相交的情况下，直接将四个值乘起来即可；而如果相交，说明可以得到更小的周长，即不可能相交。所以在已知每个面积对应的阶梯方案数下，直接做一个背包即可。
考虑每个面积对应的阶梯方案数，这是经典的分拆数问题，考虑最小的数是否是1可以得到一个\(O(n^2)\)的DP。在本题中，易证空白的面积是根号级别的（否则可以往较小的边缩），故可以通过。实际上，这个问题是五边形数对应多项式的逆，可以\(O(nlogn)\)求出：分拆数小结
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5,M=2005;
int P;
int f[M][M],g[5][M];
void init(int n){
f[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=n;j++){
f[i][j]=f[i-1][j];
if(i<=j) (f[i][j]+=f[i][j-i])%=P;
}
}
g[0][0]=1;
for(int i=1;i<=4;i++){
for(int j=0;j<=n;j++){
for(int k=0;k<=j;k++) (g[i][j]+=1ll*g[i-1][j-k]*f[n][k]%P)%=P;
}
}
//cout<<g[4][16]<<endl;
}
int T,n,op;
int cnt(int x){
return x+(n-1)/x+1;
}
struct node{
int x,s;
}p[M];
int sm,mx;
void work(){
cin>>n;
//n=4e5;
if(n==1){
if(op==1){
cout<<1<<" "<<1<<endl;
puts("#");
}
else cout<<4<<" "<<1<<endl;
return;
}
int m=(int)sqrt(n)+1,t=0,mn=n+n+2,ans=0;
for(int i=1;i<=m;i++){
int x=(n-1)/i+1;
if(x<i) continue;
//cout<<i<<" "<<j<<" "<<x<<endl;
if(i+x>mn) continue;
//cout<<i<<" "<<i+x+1<<" "<<j<<endl;
mn=i+x;
p[++t]=(node){i,i+x};
//cout<<"ans="<<ans<<endl;
}
//cout<<"t="<<t<<endl;
//sm+=t;
//mx=max(mx,t);
// return;
for(int i=t;i && p[i].s==mn;i--){
node u=p[i];
int res=n-(u.s-u.x-1)*u.x;
if(op==1){
printf("%d %d\n",u.s-u.x,u.x);
for(int j=1;j<=res;j++) putchar('#');
for(int j=res+1;j<=u.x;j++) putchar('.');
puts("");
for(int i=2;i<=u.s-u.x;i++){
for(int j=1;j<=u.x;j++) putchar('#');
puts("");
}
return;
}
//cout<<"x="<<u.x<<" s="<<u.s<<endl;
//cout<<"res="<<res<<" "<<u.x-res<<" "<<g[4][16]<<endl;
ans+=g[4][u.x-res];
if(ans>=P) ans-=P;
if(u.x!=u.s-u.x){
ans+=g[4][u.x-res];
if(ans>=P) ans-=P;
}
//cout<<ans<<endl;
}
printf("%d %d\n",mn*2,ans);
}
int main()
{
//srand(time(0));
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
cin>>T>>op;
if(op==2) cin>>P,init(1000);
while(T--) work();
//cout<<sm<<" "<<mx<<endl;
return 0;
}