HDU 1153 magic bitstrings（读题+）

　hdu 1153 magic bitstrings

题目大意

一个质数p，现在让你求一个p-1长度的“01魔法串”。关于这个魔法串是这么定义的：
我们现在把这个串经过一段处理变成一个长宽均为p-1的矩阵，对于第i行的串，是由原来的串按每i位取得的。如果这个矩阵每行的串满足：和原来的串相等或是原来的串按位取反，我们就称这个串是魔法串。（说了一大堆如果还没看懂就去问题底下的Discuss看吧….）

题解

一开始热衷于讨论第一行和最后一行的关系…结果什么也没看出来…后来看了别人的题解，才发现自己有多蠢。
我们把前两行先写出来：

Column1	Column2	…	Columnp−1
a1.mod.p	a2.mod.p	…	ap−1
a2.mod.p	a4.mod.p	…	a[2∗(p−1)].mod.p

我们可以看到，讨论表格前两列的话 a1.mod.p 和 a2.mod.p 如果相等，那么 a2.mod.p 和 a4.mod.p 一定也相等，所以我们得到 a1.mod.p 和 a4.mod.p 相等；而如果 a1.mod.p 和 a2.mod.p 不相等的话，我们同样推出 a1.mod.p 和 a4.mod.p 相等，所以 a1.mod.p 和 a4.mod.p 一定是相等的。
同理可以得到 a1.mod.p 和 a9.mod.p 相等、 a1.mod.p 和 a16.mod.p 相等…..所以我们得出一个结论： ai2.mod.p 都是相等的，其余各项也都是相等的。
为了字典序最小，我们把所有 ai2.mod.p 置为0，其余各项置为1，除了2以外，对于所有的质数都是有解的。

把矩阵列出来

a[1%n], a[2%n], a[3%n], ..., a[n-1] (1)

a[2%n], a[4%n], a[6%n], ..., a[2(n-1)%n] (2)

a[3%n], a[6%n], a[9%n], ..., a[3(n-1)%n] (3)

...

比较 (1), (2)

发现：

如果 a[1%n] != a[2%n]，那么 a[2%n] != a[4%n]，那么 a[1%n] == a[4%n]；

如果 a[1%n] == a[2%n]，那么 a[2%n] == a[4%n]，那么 a[1%n] == a[4%n]。

所以 a[1%n] == a[4%n]

同样的方法得到：

a[1%n] == a[9%n],

a[1%n] == a[16%n],

....

所有下标是 i 平方 mod n 都相等。

下标不是 i 平方 mod n 都相等。

为了字典顺序最小，并且避免整个数列都是同一个数（题目要求 non-constant），令 a[1%n] = a[4%n] = a[9%n] = ... = 0，其他数都是 1，这样符合题意。

#include <iostream>

#include <cstring>

#include <cstdio>

#define LL long long

using namespace std;

LL p;

bool flag[];

int main()

{

    while(scanf("%I64d",&p),p!=)

    {

        memset(flag,,sizeof(flag));

        if (p==)

        {

            printf("Impossible\n");

            continue;

        }

        for (LL i=;i<p;i++) flag[(i*i)%p]=;

        for (int i=;i<p;i++) printf("%d",!flag[i]);

        printf("\n");

    }

    return ;

}

#include <iostream>

#include <iterator>

#include <algorithm>

#include <vector>

int main () {

    long long p;

    while ((std::cin >> p) && p) {

        if (p == ) {

            std::cout << "Impossible\n";

            continue;

        }

        std::vector <int> v (p, );

        for (long long i=; i<p; ++i) {

            v [i * i % p] = ;

        }

        std::copy (v.begin() + , v.end(), std::ostream_iterator <int> (std::cout));

        std::cout << "\n";

    }

    return ;

}

巴特西

HDU 1153 magic bitstrings（读题+）

题目大意

题解

最新文章

热门文章