PKU 2356 Find a multiple

http://poj.org/problem?id=2356
n個の数字から1個以上の数字を選んでその和がnの倍数になるようにしろというような問題。

枝刈りdfsしました。
n=100000くらいの似たような問題だとTLEして通らないのが悲しいです。

int ans[20000];
int sz;
int n;
int in[10000];
int vis[10000];

bool dfs(int ne,int v){
  //cout<<ne<<' '<<v<<endl;
  if(ne && !v)return true;
  if(v)vis[v]=ne;

  for(int i=ne;i<n;++i){
    if(vis[(v+in[i])%n]!=-1 && vis[(v+in[i])%n]<=i)continue;
    if(dfs(i+1,(v+in[i])%n)){
      ans[sz++]=in[i];
      return true;
    }
  }
  return false;
}

main(){
  cin>>n;
  rep(i,n)cin>>in[i];
  memset(vis,-1,sizeof(vis));
  dfs(0,0);
  cout<<sz<<endl;
  rep(i,sz)cout<<ans[i]<<endl;
}