Solution for Live Archive 6529 - Eleven

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=602&page=show_problem&problem=4410

I have solved this problem using the divisibility check rule of 11
Form the alternating sum of the digits.
918,082: 9 − 1 + 8 − 0 + 8 − 2 = 22. and 22 is divisible by 11.
http://en.wikipedia.org/wiki/Divisibility_rule

using this observation, I have built a dp solution to get the number of ways. The dp state is the remaining pluses, the remaining minus, cur number (0-9), and sum till now.

/*
 * 6529.cpp
 *
 *  Created on: Jul 30, 2014
 *      Author: ghooo
 */

#include <cstring>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <vector>
#include <set>
#include <complex>
#include <list>
#include <climits>
#include <cctype>
#include <bitset>
//#include <windows.h>

using namespace std;

#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define sz(v) ((ll)v.size())
#define rep(i,m) for(int i=0;i<(int)(m);++i)
#define rep2(i,n,m) for(int i=n;i<(int)(m);i++)
#define For(it,c) for(__typeof(c.begin()) it=c.begin();it!=c.end();++it)
#define reset(a,b) memset(a,b,sizeof(a))
#define mp make_pair
#define dot(a,b) ((conj(a)*(b)).X)
#define X real()
#define Y imag()
#define length(V) (hypot((V).X,(V).Y))
#define vect(a,b) ((b)-(a))
#define cross(a,b) ((conj(a)*(b)).imag())
#define normalize(v) ((v)/length(v))
#define rotate(p,about,theta) ((p-about)*exp(point(0,theta))+about)
#define pointEqu(a,b) (comp(a.X,b.X)==0 && comp(a.Y,b.Y)==0)
#define clrq(x) while(!x.empty()) x.pop();
#define clrvv(v) rep(i,sz(v))v[i].clear();
#define debug(x) cerr << #x << ": " << x << endl;
#define debugv(v) cerr << #v << ": ";For(it,v)cerr <<(*it)<<", "; cerr<<endl;

typedef stringstream ss;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<string> vs;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<vector<int> > vii;
typedef long double ld;
typedef complex<double> point;
typedef pair<point, point> segment;
typedef pair<double, point> circle;
typedef vector<point> polygon;
typedef unsigned long long ull;
typedef long long ll;

//==============================================================
// handling triples
typedef pair<ll,pair<ll,ll> > triple;
#define tfirst first
#define tsecond second.first
#define tthird second.second
#define mt(x,y,z) mp(x,mp(y,z))
//---------------------------------------------------------------

const int oo = (int) 1e9;
const double PI = 2 * acos(0.0);
const double eps = 1e-9;
const ll MOD = (int)1e9 + 7;
ll mem[51][51][10][11];
int vis[51][51][10][11],ID;
int cnt[10];
string t;
ll memnCr[100][100];
ll nCr(ll n, ll r){
 if(r == 0) return 1;
 if(r == 1) return n;
 if(n == r) return 1;
 ll &ret = memnCr[n][r];
 if(ret) return ret;
 return ret = (nCr(n-1,r)+nCr(n-1,r-1))%MOD;
}
ll dp(int p, int m, int cur, int rem){
 if(cur == 10){
  return rem%11 == 0;
 }
 ll &ret = mem[p][m][cur][rem];
 if(vis[p][m][cur][rem] == ID) return ret;
 vis[p][m][cur][rem] = ID;
 ret = 0;
 rep2(i,max(0,cnt[cur]-p),min(cnt[cur],m)+1){
  ll tmp = (dp(p-(cnt[cur]-i),m-i,cur+1,(rem-i*cur+(cnt[cur]-i)*cur+11*11*11)%11))%MOD;
  tmp = (((nCr(m,i)*nCr(p,cnt[cur]-i))%MOD*tmp)%MOD);
  ret = (ret+tmp)%MOD;
 }
 return ret;
}
ll fact(ll n){
 ll ret = 1;
 rep2(i,2,n+1)ret = (ret*i)%MOD;
 return ret;
}
int main(){
 ios_base::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
 freopen("in.txt", "r", stdin);
 //freopen("out.txt", "w", stdout);
#endif
 string s;
 while(cin >> s){
  reset(cnt,0);
  rep(i,sz(s)) cnt[s[i]-'0']++;
  ll ans = 0;
  rep2(i,1,10){
   if(cnt[i] == 0) continue;
   cnt[i]--;
//   reset(mem,-1);
   ID++;
   ans = (ans+dp((sz(s)-1)/2, sz(s)/2,0,i))%MOD;
   cnt[i]++;
  }
  cout << ans << endl;
 }

 return 0;
}