2019-team2/Sp077

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[[Image(1.png,700px)]]

[[Image(2.png,700px)]]



[http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001537]

[wiki:2019-team2 返回Runespoor]

== 流水账 ==


== 总结 ==

'''zqq: ''' 今天前期比较顺利

            今天榜非常奇怪，后期只有两题可做。就扎进去想：
                A是一个三进制mex卷积。我有学习了一遍K进制异或卷积，感觉自己懂了原理。但是不会推这个。但最后想到补位到4进制，但是没有仔细推。结果一不小心搜到了原题。然后就学习了一下做法。比赛强制结束。还是很不应该，应该再想想的，毕竟还有40分钟。

                J是一个不断猜结论的题目，一开始heltion和lyk讨论。搞出了一个奇怪的bitset做法。后来我加入讨论，lyk就上机写了。写到一半我发现是一个hash。我认为这个bitset的（3000^3^ / 64复杂度太大了，过不去）。'''实在不行试一下可以，但是同时还是必须想别的做法！！'''

=== 题解 ===

* A ： https://www.cnblogs.com/yuanquming/p/11804462.html 找一个变换，使得可以成功分拆。如果不能则考虑添加一位。

* J :  如果没有问号，我们直接统计每个位置合法的变换位置集合（相同的放一起），方案数是每组个数的阶乘乘起来（注意每组出发和到达要相同，否则为0）。这个直接hash，把相同hash值的丢到map里面就好。

       因为问号改成a的方案和问号改成b的方案的交一定是问号单独看成一个字符的答案（多个的交也是）。所以可以容斥。答案 = ？看成每个字符的答案和 - ？看成单独特殊字符的答案 * （字符集 - 1）


=== 补题 ===

http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001537

返回Runespoor

流水账

总结

zqq: 今天前期比较顺利

今天榜非常奇怪，后期只有两题可做。就扎进去想：

A是一个三进制mex卷积。我有学习了一遍K进制异或卷积，感觉自己懂了原理。但是不会推这个。但最后想到补位到4进制，但是没有仔细推。结果一不小心搜到了原题。然后就学习了一下做法。比赛强制结束。还是很不应该，应该再想想的，毕竟还有40分钟。

J是一个不断猜结论的题目，一开始heltion和lyk讨论。搞出了一个奇怪的bitset做法。后来我加入讨论，lyk就上机写了。写到一半我发现是一个hash。我认为这个bitset的（3000³ / 64复杂度太大了，过不去）。实在不行试一下可以，但是同时还是必须想别的做法！！

题解

A ： https://www.cnblogs.com/yuanquming/p/11804462.html 找一个变换，使得可以成功分拆。如果不能则考虑添加一位。
J : 如果没有问号，我们直接统计每个位置合法的变换位置集合（相同的放一起），方案数是每组个数的阶乘乘起来（注意每组出发和到达要相同，否则为0）。这个直接hash，把相同hash值的丢到map里面就好。

因为问号改成a的方案和问号改成b的方案的交一定是问号单独看成一个字符的答案（多个的交也是）。所以可以容斥。答案 = ？看成每个字符的答案和 - ？看成单独特殊字符的答案 * （字符集 - 1）