Artifact Content
Not logged in

Artifact c64847afba8ca911f9978b4a7f4165f4c8bac0a5


#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
using namespace std;
typedef long long LL;
typedef long double LD;
typedef complex<LD> CMP;

static const int MODVAL = 1000000007;
struct mint
{
	int val;
	mint():val(0){}
	mint(int    x):val(x%MODVAL) {}
	mint(size_t x):val(x%MODVAL) {}
	mint(LL     x):val(x%MODVAL) {}
};
mint& operator+=(mint& x, mint y) { return x = x.val+y.val; }
mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; }
mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; }
mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; }
mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); }
mint operator+(mint x, mint y) { return x+=y; }
mint operator-(mint x, mint y) { return x-=y; }
mint operator*(mint x, mint y) { return x*=y; }
mint operator/(mint x, mint y) { return x/=y; }
vector<mint> FAC_(1,1);
mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() ); return FAC_[n]; }
vector< vector<mint> > CP_; // Pascal's triangle: if O(1) nCk is needed.
mint C(LL n, LL k) {
	while( CP_.size() <= n ) {
		int nn = CP_.size();
		CP_.push_back(vector<mint>(nn+1,1));
		for(int kk=1; kk<nn; ++kk)
			CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk];
	}
	return k<0 || n<k ? 0 : CP_[n][k];
}

template<typename T>
struct DP3
{
	int N1, N2, N3;
	vector<T> data;
	DP3(int N1, int N2, int N3, const T& t = T())
		: N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T)<(1<<26)); }
	T& operator()(int i1, int i2, int i3)
		{ return data[ ((i1*N2)+i2)*N3+i3 ]; }
	void swap(DP3& rhs)
		{ data.swap(rhs.data); }
};

class ElevenMultiples { public:
	// (10^p)%11
	int rem11(int p)
	{
		return p%2==0 ? 1 : 10;
	}

	int countMultiples(vector <string> pieces)
	{
		vector<int> es, os;
		for(int i=0; i<pieces.size(); ++i) {
			int r = 0;
			for(int k=0; k<pieces[i].size(); ++k)
				r = (r + (pieces[i][k]-'0')*rem11(k)) % 11;
			(pieces.size()%2==0 ? es : os).push_back(r);
		}
		return solve(es, os).val;
	}

	mint solve(const vector<int>& es, const vector<int>& os)
	{
		DP3<mint> dpE(es.size(), 11, es.size()+1);
		int rE = accumulate(es.begin(), es.end(), 0) % 11;
		for(int i=0; i<es.size(); ++i)
		for(int r=0; r<11; ++r)
		for(int n=0; n<=es.size(); ++n)
		{
			int v = es[i];
			if(i==0) {
				if(r==0 && n==0 || r==v && n==1)
					dpE(i,r,n) = 1;
			} else {
				if(n>0)
					dpE(i,r,n) = dpE(i-1,r,n) + dpE(i-1, (r-v+11)%11, n-1);
				else
					dpE(i,r,n) = dpE(i-1,r,n);
			}
		}
		DP3<mint> dpO(os.size(), 11, os.size()+1);
		int rO = accumulate(os.begin(), os.end(), 0) % 11;
		for(int i=0; i<os.size(); ++i)
		for(int r=0; r<11; ++r)
		for(int n=0; n<=os.size(); ++n)
		{
			int v = os[i];
			if(i==0) {
				if(r==0 && n==0 || r==v && n==1)
					dpO(i,r,n) = 1;
			} else {
				if(n>0)
					dpO(i,r,n) = dpO(i-1,r,n) + dpO(i-1, (r-v+11)%11, n-1);
				else
					dpO(i,r,n) = dpO(i-1,r,n);
			}
		}

		mint total = 0;
		for(int re=0; re<11; ++re)
		for(int ne=0; ne<=es.size(); ++ne)
		for(int ro=0; ro<11; ++ro)
		for(int no=0; no<=os.size(); ++no)
		{
			int re2 = (rE - re + 11)*10%11;
			int ne2 = es.size() - ne;
			int ro2 = (rO - ro + 11)*10%11;
			int no2 = os.size() - no;
			if((re + re2 + ro + ro2)%11 == 0)
			if( ne2+no2==0 || no>0 )
			if(no==no2 || no==no2+1) {
				mint choice = (es.empty() ? re==0?1:0 : dpE(es.size()-1, re, ne))
					* (os.empty() ? ro==0?1:0 : dpO(os.size()-1, ro, no));
				total += choice * cnt(ne, ne2, no, no2);
			}
		}
		return total;
	}

	mint cnt(int ne, int ne2, int no, int no2)
	{
		mint x = FAC(no) * FAC(no2);
		int nec = (no==no2 ? no+1 : no);
		int ne2c = no;
		return x * dist(nec, ne) * dist(ne2c, ne2);
	}

	mint dist(int n, int k)
	{
		return FAC(n) * C(n+k-1, k-1);
	}
};

// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
 { os << "{ ";
   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
 bool ok = (Expected == Received);
 if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END	 verify_case(_, ElevenMultiples().countMultiples(pieces));}
int main(){

CASE(0)
	string pieces_[] = {"58", "2012", "123"};
	  vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_)); 
	int _ = 2; 
END
CASE(1)
	string pieces_[] = {"1", "1111", "1", "11"};
	  vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_)); 
	int _ = 24; 
END
CASE(2)
	string pieces_[] = {"43925486943738659795389387498953274"};
	  vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_)); 
	int _ = 1; 
END
CASE(3)
	string pieces_[] = {"983", "4654", "98", "3269", "861", "30981"};
	  vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_)); 
	int _ = 96; 
END
CASE(4)
	string pieces_[] = {"193", "8819", "40676", "97625892", "5719", "45515667", "32598836", "70559374", "38756", "724",
"93391", "942068", "506", "901150", "874", "895567", "7560480", "7427691", "799450", "85127"};
	  vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_)); 
	int _ = 537147821; 
END
CASE(5)
	string pieces_[] = {"687045939630", "997856158148599044", "2014910234712225061", "9658113323175370226", "1584118137",
"67925153345598920", "6960366756", "863413844386808834", "799302243562410012", "44481835751",
"8004606814733183", "19623906615609", "23859998326058162", "461385591582", "9261878982390119",
"1569373294276", "318106951168934", "65389049931", "12791173342", "507877942026",
"3947173045690", "472425746178910", "524552931853595", "40771812249667850232", "563988469071932",
"28147819070", "797007158858587", "5716177008624223", "387565700495309324", "4716621063133318"}
;
	  vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_)); 
	int _ = 814880650; 
END
/*
CASE(6)
	string pieces_[] = ;
	  vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_)); 
	int _ = ; 
END
CASE(7)
	string pieces_[] = ;
	  vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_)); 
	int _ = ; 
END
*/
}
// END CUT HERE