本文主要是介绍【HDU】 1153 Magic Bitstrings,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Magic Bitstrings
题目链接
- 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以外,对于所有的质数都是有解的。
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#define LL long longusing namespace std;LL p;
bool flag[1000005];int main()
{while(scanf("%I64d",&p),p!=0){memset(flag,0,sizeof(flag));if (p==2){printf("Impossible\n");continue;}for (LL i=1;i<p;i++) flag[(i*i)%p]=1;for (int i=1;i<p;i++) printf("%d",!flag[i]);printf("\n");}return 0;
}
这篇关于【HDU】 1153 Magic Bitstrings的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!