思ったより難しかった。明日がSRMなので最後の調整。
解説（
soul-netの解説は好きな方なんだけど）でも良くわからなくて苦労した。
ここでは、「相手のターンでこのコイン数だったら勝てる」をtoWin（Wとする）、そうでなければtoLose（Lとする）とする。調べたいコイン数nにおいて、n - moves[i] = toWin[j]となるi,jの組が一つでもあればnはtoLose入り、そうでなければtoWin入り。movesでループして引き算の結果がtoWinに含まれているか調べればよい（toWinをArrayListにしておけばcontainsで調べられる）。これを繰り返せばO(maxN*moves.length)だが、解説にもあるとおり多すぎ。しかし、これがtoWin, toLoseを調べる基本。toWinの初期値はmovesがソートさえているとして0～moves[0]（最も小さい数）で、moves[0]+1から順に調べていけばいい。
n - moves[i] = toWin[j]を調べるのだから、nを調べるのに参照する数字はn-moves[0]～n-moves[moves.length-1]。実はそれ以外の数は必要ではない。だから、何とかすればどこかから繰り返しになるはずなのだが、その繰り返しを見つける方法が分からなかった。
解説にあるように、nから最も離れていてnのチェックに使う数字はn-moves[moves.length-1]。これをn-lenとする。ここで、まじめに考えるとチェックに使う数字は連続でなくてmoves.length個しかないのだが、敢えて連続したlen個の数字に着目するのがミソ。toWinに含まれていたらW、でなければLというステータスをn-len ～ n-1の数字で調べると以下のようになる。
WLWWWLWWLLW？
n-len.....................n-1 n
全ての i において n - moves[i] が全てLのときｎにWステータスがつくわけで、movesの間の数は関係ないのだが敢えて調べておく。今回nはWだったとすると、今後"WLWWWLWWLLW"と続いたら次は必ずWとなる。するとn+1はWLWWWLWWLLW
W？でしらべ、これがLだとすると、今度は"LWWWLWWLLW
W"が続いたら次は必ずLなわけである。こうしてキャタピラのように進んでいって、同じ長さlenのWLの組み合わせが1度でも登場すれば、そこから先は全て繰り返しな訳である。
だから、上記のW/Lチェックと同時にn-len～n-1のW/Lステータスをビットで表現（maskとする）して、mem[mask]に今のnを入れておく。もし、mem[mask]に既に数字Nが入っていたら、N～n-1がmaxNまで繰り返されると思えばよい。
あとは、0を含めた0～maxNの数字のループ内・ループ外を計算すばよくて、loop = N-nとすると(maxN+1-N)/loopがループの数で、同時に調べていたtoWinにこのループ内の数字がいくつ入っていたか調べれば（countとする）、ループ内の対象数はcount*((int)(maxN+1-N)/loop)。あとはループの前後を丁寧に数える。0～N-1でtoWinに入っている数を数えて足し、loop*((int)(maxN+1-N)/loop)～maxNの数JでJ-loop*((int)(maxN+1-N)/loop)がtoWinに入っている数を足し、最後に０を除外（０は必ず入っているので素直に1引く）すれば答え。
public class LongLongNim
{
public int numberOfWins(int maxN, int[] moves)
{
Arrays.sort(moves);
TreeSet＜Integer＞ toWin = new TreeSet＜Integer＞();
TreeSet＜Integer＞ toLose = new TreeSet＜Integer＞();
for(int i=0;i＜moves[0];i++){toWin.add(i);}
int max = moves[moves.length-1];
int[] mem = new int[1＜＜(max+1)];
Arrays.fill(mem, -1);
int start = -1; int end = -1;
for(int i=0;;i++){
boolean hit = false;
for(int j=0;j＜moves.length && i＞=moves[j] && !hit;j++){
if(toWin.contains(i-moves[j])){
toLose.add(i);
hit=true;
}
}
if(!hit){toWin.add(i);}
int mask = 0;
for(int j=1;j＜=max;j++){
if(toWin.contains(i-j)){mask |= (1＜＜j);}
}
if(mem[mask]==-1){
mem[mask]=i;
}else{
start = mem[mask];
end = i-1;
break;
}
}
int count = 0;
for(int i=start;i＜=end;i++){if(toWin.contains(i))count++;}
int loop = end-start+1;
int d = (maxN-start+1)/loop;
int ret = d*count;
for(int i=0;i＜start;i++)if(toWin.contains(i)){ret++;}
for(int i=start+d*loop;i＜=maxN;i++) {
if(toWin.contains(i-d*loop)){ret++;}
}
return ret-1;
}
}
