cafelier@SRM

SRM500 1000

あとで | 06:48 |

• 意外と、やるだけ問題だった

static const int MODVAL = 500500573; // prime
struct mint
{
   int val;
   mint():val(0){}
   mint(int x):val(x%MODVAL) {}
   mint(LL  x):val(x%MODVAL) {}
};
mint operator+(mint x, mint y) { return x.val+y.val; }
mint operator-(mint x, mint y) { return x.val-y.val+MODVAL; }
mint operator*(mint x, mint y) { return LL(x.val)*y.val; }
mint POW(mint x, int e) {
   mint v = 1;
   for(;e;x=x*x,e>>=1)
      if(e&1)
         v=v*x;
   return v;
}
mint operator/(mint x, mint y) { return x * POW(y, MODVAL-2); }

class ProductAndSum { public:
   int getSum(int p2, int p3, int p5, int p7, int S) 
   {
      // Precompute n!, 1/n!, and 111...111
      vector<mint> FACT(2501), FACT_INV(2501), ONES(2501);
      FACT[0] = FACT_INV[0] = 1;
      ONES[0] = 0;
      for(int n=1; n<FACT.size(); ++n)
      {
         FACT[n] = FACT[n-1] * n;
         FACT_INV[n] = 1 / FACT[n];
         ONES[n] = ONES[n-1]*10 + 1;
      }

      mint answer = 0;

      // Exhaustive search over the numbers of 4,6,8,9s : approximately 33*50*50*100/4 ~ 2M iterations
      for(int v8=0; v8*3<=p2; ++v8)
      for(int v4=0; v4*2+v8*3<=p2; ++v4)
      for(int v9=0; v9*2<=p3; ++v9)
      for(int v6=0; v6+v4*2+v8*3<=p2 && v6+v9*2<=p3; ++v6)
      {
         // then, the numbers of 1,2,3s will follow
         int v[] = {-1, -1, p2-v8*3-v4*2-v6, p3-v9*2-v6, v4, p5, v6, p7, v8, v9};
         {
            int v1 = S;
            for(int i=2; i<=9; ++i)
               v1 -= i * v[i];
            if( v1 < 0 )
               continue;
            v[1] = v1;
         }
         int N = accumulate(v+1, v+10, 0);

         // Now, let's compute the sum of all integers, who have N digits and #d = v[d], in constant time!

         // It can be calculated as follows:
         //   Q: how many of the integers have, say "1" in the last digit?
         //   A: it is, of course, C(N-1, v[1]-1, v[2], ..., v[9])
         //      where C(k,a,b,..) is the # of ways of spliting k elements into groups of size a, b, ...
         // So, the sum of the least digits of the integers are
         //   X = \Sigma_{d=1..9} (d * C(N-1, v[1], v[2], ..., v[d]-1, ..., v[9]))
         // By the same argument, the sum of the second-last digits (10-no-kurai in japanese) is
         //   10 * X
         // For hundreds, the sum is 100*X, and so on. Eventualy, the sum of whole integers is
         //   t = (1+10+...+10^N) * X
         //     = 111...111 * \Sigma_{d=1..9} (d * C(N-1, v[1], v[2], ..., v[d]-1, ..., v[9]))
         // Let us simplify the formula by using C(k,a,b,...) = k! / a!b!...
         //   t = 111...111 * \Sigma_{d=1..9} (d * (N-1)! / v[1]! / ... / v[9]! * v[d])
         //     = 111...111 * (N-1)! / v[1]! / ... / v[9]! * \Sigma_{d=1..9} (d*v[d])
         //     = 111...111 * (N-1)! / v[1]! / ... / v[9]! * S
         // That's it!
         mint t = ONES[N] * FACT[N-1] * S;
         for(int i=1; i<=9; ++i)
            t = t * FACT_INV[v[i]];
         answer = answer + t;
      }
      return answer.val;
   }
};

• 1の個数, 2の個数, ..., 9の個数, が決まれば式一発で求まるので、
• その個数として可能なパターンを全部試せばいい。
  • 総和がS, p2, p3, p5, p7 の 5 つの条件式があって
  • 9変数
• なので、4変数の固定のしかたを全通り試せば残りの変数は決まる
• ということで、4,6,8,9の個数が自由度少なめなのでそれを全部動かしてみるとせいぜい2Mパターン。行ける。