Draupnir - Click Here
Description
Odin has some magical rings which produce copies of themselves. Each “X-day ring” produces one more X-day ring every X days after the day it came into existence. These rings come in six possible varieties: 1-day, 2-day, …, all the way up to 6-day.
For example, a 3-day ring that came into existence on day 0 would do nothing until day 3, when it would produce another 3-day ring. Then, on day 6, each of those two rings would produce another 3-day ring, and so on.
You know that Odin had no rings before day 0. On day 0, some rings came into existence. At the end of day 0, Odin had Ri i-day rings, for each $1 \leq i \leq 6$. You know that $0 \leq R_i \leq 100$, for all $i$, and at least one of the $R_i$ values is positive.
Fortunately, you also have access to the secret well of knowledge. Each time you use it, you can find out the total number of rings that Odin had at the end of a particular day between day 1 and day 500, inclusive. The well will give you the answer modulo $2^{63}$, because even it can only hold so much information! Moreover, you can only use the well up to W times.
Your goal is to determine how many rings of each type Odin had at the end of day 0 — that is, you must find each of the $R_i$ values.
Test set 1: W = 6
Test set 2: W = 2
Solutions
挺有趣的一道题目…当初肝了快1h吧…
一种比较显然的做法是，直接询问$6$次得到一个线性方程组。
这样就能直接解出$R_i$，但这只能过小数据。
因此从方程组角度是无法得到更优做法的。
考虑一些乱搞做法。可以随意取两个奇怪的天数，这样一个六元组就能用这两个答案表示。最后只需要做两次询问，并反演一下得到六元组？
但这样子做是不太行的。因为模数是$2^{63}$，而每个元素的系数都是$2$的幂次，这时候我们用于对应的二元组就很容易发生冲突。
从冲突的角度重新思考下这道题。因为每个系数都是$2$的幂次，而每个元素的范围不超过$100$。这表明，如果选取的天数比较大的话，相邻两个元素的系数差会远超过$100$，这时候只需要简单的位运算即能求出元素的具体数值。
因此，只需要选取第$56$天和第$224$天就能得到$R_1,R_2,R_3$和$R_4,R_5$的具体数值。再利用第$56$天的数据，解出$R_3$即可。
CODE
CODE - Click Here