H********g
发帖数: 43926 | 1 两个字符 a和b 可以形成2^2个长度为2的词 ab, ba, aa, bb
如果给你一个长度为4的空字符串 让你往里填 a和b 使得 ab ba bb aa 各至少出现
一次 这是不行的 因为4字的串里只有3个2字词 但是如果允许这个字符串首尾相
接环化 那就可以了 比如abba 环化即可
那问题来了： 假如有n个不同的字符 然后给你一个 长度n^n 首尾相接成环的空字符
串 你总有办法 使得所有长度为n的字符串在这个n^n长度的字符环里都出现一次吗？ |
H********g
发帖数: 43926 | 2 问题升级：
如果字符总数是n 那它们可以组成的 长度为m的词的总数是n^m
现在给你一个长度是n^m的空环 你总可以让这所有长度m的词在这个环里出现一次吗
【在 H********g 的大作中提到】
: 两个字符 a和b 可以形成2^2个长度为2的词 ab, ba, aa, bb
: 如果给你一个长度为4的空字符串 让你往里填 a和b 使得 ab ba bb aa 各至少出现
: 一次 这是不行的 因为4字的串里只有3个2字词 但是如果允许这个字符串首尾相
: 接环化 那就可以了 比如abba 环化即可
: 那问题来了： 假如有n个不同的字符 然后给你一个 长度n^n 首尾相接成环的空字符
: 串 你总有办法 使得所有长度为n的字符串在这个n^n长度的字符环里都出现一次吗？
|
t******g
发帖数: 10390 | 3 4个就破了吧
没法同时出现bacd，abcd
【在 H********g 的大作中提到】
: 两个字符 a和b 可以形成2^2个长度为2的词 ab, ba, aa, bb
: 如果给你一个长度为4的空字符串 让你往里填 a和b 使得 ab ba bb aa 各至少出现
: 一次 这是不行的 因为4字的串里只有3个2字词 但是如果允许这个字符串首尾相
: 接环化 那就可以了 比如abba 环化即可
: 那问题来了： 假如有n个不同的字符 然后给你一个 长度n^n 首尾相接成环的空字符
: 串 你总有办法 使得所有长度为n的字符串在这个n^n长度的字符环里都出现一次吗？
|
B********u
发帖数: 1 | 4 4^4= 256
【在 t******g 的大作中提到】
: 4个就破了吧
: 没法同时出现bacd，abcd
|
t******g
发帖数: 10390 | 5 土 我理解错了
【在 B********u 的大作中提到】
: 4^4= 256
|
H********g
发帖数: 43926 | 6 暴力法说明，n=4, m=4 是可以的
[00............3]
[
0000100020003001100120013002100220023003100320033011101011201020113010301210
1220123013101320133021102120202130203022102220223023102320233031103120313030
3210322032303310332033311112111311221123113211331212131222122312321233131322
1323133213332222322332323333]
[00............3] |
H********g
发帖数: 43926 | 7 试了各种n 和m 似乎总是可以的 而且对于一对n和m应该有多种不同的环
但是怎么证明呢？
0000100020003001100120013002100220023003100320033011101011201020113010301210
1220123013101320133021102120202130203022102220223023102320233031103120313030
3210322032303310332033311112111311221123113211331212131222122312321233131322
【在 H********g 的大作中提到】
: 暴力法说明，n=4, m=4 是可以的
: [00............3]
: [
: 0000100020003001100120013002100220023003100320033011101011201020113010301210
: 1220123013101320133021102120202130203022102220223023102320233031103120313030
: 3210322032303310332033311112111311221123113211331212131222122312321233131322
: 1323133213332222322332323333]
: [00............3]
|
