Because it is a "coding interview", not acm/icpc or other competitions. Similar to Josephus Cycle, I prefer LinkedList Cycle than Mod-Method during interviews. Here's a backtraking-dp solution.

```
public class Solution {
public boolean canWinNim(int n) {
if(n>=134882061){//I have no any other ways,please forgive my unchastity(无节操)!
return n%4 != 0;
}
int[] array=new int[n+1];
return dfs(n, array);
}
public boolean dfs(int n,int[] array){
if(array[n]!=0){
return array[n]==1?true:false;
}
if(n<=3){
array[n]=1;
return true;
}else{
for(int i=1;i<=3;i++){
if(!dfs(n-i,array)){
array[n-i]=-1;
array[n]=1;
return true;
}
}
array[n]=-1;
return false;
}
}
}
```