HDU 6313 2018多校第二场hack it

10000 10000 10000 10000 10000

10000 01000 00100 00010 00001

10000 00100 00001 01000 00010

10000 00010 01000 00001 00100

10000 00001 00010 00100 01000 

01000 01000

01000 00100

dls:类似的构造遇到过几次了，orz，听了dls的构造方法，对于一个块，行数为p(质数)，列数为p*p，列又分为p段，每段p个，然后对于整个大正方形矩阵，就有n/p个这样的块，第一个块的的一段都是1开始，第二个块的第一段都是2开始...然后同一个块中，每一段的每一行的位置都是上一段同一行的位置+段的编号再%p。

就这样一个构造法，最后取前2000*2000的矩阵，最后我写check发现是85105个1。

我们可以发现，对于每一个块，除了第一段是1在一条线上的，其他每段都是一个没有1在一条线上的p的排列。

对于每一块的同一段从上往下看1的排列，其实一共有A(p,p)种，就是p！种，远远大于总共的p块*(p-1)段，其实每一块的每一块p*每一段（p-1）只要去这些排列中不同的就行了，但是使用dls的构造方法就可以开心地得到上述结果。（好像直接dfs出p*p个矩阵也星)由于p要是质数，43*43<2000，那么我们就去47*47了，然后在输出前2000*2000的矩阵。注意一个问题是printf数字要比printf一个char数组慢太多了。。。4*1e6的printf要6s多。。。scanf是不是也这么慢的。。。

给一个证明链接：https://blog.csdn.net/AC_hunter/article/details/81214033#commentsedit

------update:好像直接dfs出p*p个p排列的矩阵随意放置是不行的，需要特殊的放置技巧，来放置这些p排列的矩阵，不过好像没撒好的想法，还是dls这个构造方法强

#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxl 3010

using namespace std;

char a[maxl][maxl];


int main()
{
//	freopen("1005.out","w",stdout);
	int n=47;
	int x,y;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			for(int k=0;k<n;k++)
			{
				x=i*n+j;y=(i+j*k)%n+k*n;
				a[x][y]='1';
			}
	for(int i=0;i<2000;i++)
	{
		for(int j=0;j<2000;j++)
		if(a[i][j]!='1')
			a[i][j]='0';
		a[i][2000]=0;
	}
	puts("2000");
	for(int i=0;i<2000;i++)
	{
		printf("%s\n",a[i]);
	}
	return 0;
}