题解：P12706 并非呃呃

· · 题解

难度可能有些虚高吧。

前两个数据点可以自己比较容易进行构造，所以直接考虑构造 n=2333，L=10^5 的即可。

发现 n^{\frac{3}{2}}\approx112687>10^5，1 的个数占比约为 \frac{1}{\sqrt{n}}。考虑将这个 n\times n 的正方形分为 n^{\frac{3}{2}} 个 1\times\sqrt{n} 矩形，每个矩形中有且仅有 1 个 1。我们将第 i 个元素为 1 的矩形看作 i。这样，我们就可以将问题转化为：构造 n 个 \sqrt{n} 元组 (x_{i,1},x_{i,2},\dots,x_{i,\sqrt{n}})，满足：

然后构造就简单得多了：将块长设为 47（多的那部分不用管了，弄成 0 即可），将其分为 47 组，每组 47 行，对于第 i 组中的第 k 行的第 j 个矩形，将这个矩形中第 (i\times j+k)\bmod 47 个数变为 1 即可。共有 47^3=103823 个 1 符合题意。

代码：

#include<bits/stdc++.h>
#define puts(x) printf(x);printf("\n")
using namespace std;
bitset<2500>e;
int n,L;
int main()
{
    scanf("%d%d",&n,&L);
    if(n==4){
        puts("1100");
        puts("1001");
        puts("0110");
        puts("0011");
        return 0;
    }else if(n==10){
        puts("0011000000");
        puts("0110000000");
        puts("1100000000");
        puts("1001000000");
        puts("1000110000");
        puts("0100011000");
        puts("1000001100");
        puts("0100000110");
        puts("1000000011");
        puts("0100100001");
        return 0;
    }
    for(int i=0;i<47;++i){
        for(int k=0;k<47;++k){
            for(int j=1;j<=2333;++j)e[j]=false;
            for(int j=0;j<47;++j){
                e[j*47+1+(i*j+k)%47]=true;
            }
            for(int j=1;j<=2333;++j){
                if(e[j]==true)putchar('1');
                else putchar('0');
            }
            putchar('\n');
        }
    }
    for(int i=47*47+1;i<=2333;++i){
        for(int j=0;j<2333;++j){
            putchar('0');
        }
        putchar('\n');
    }
    return 0;
}/*

*/