fork download
copy 
  1. // BEGIN CUT HERE
  2.  
  3. // END CUT HERE
  4. #line 5 "SumProduct.cpp"
  5. #include <bits/stdc++.h>
  6. #define LL long long
  7.  
  8. using namespace std;
  9.  
  10. const LL mod = 1e9 + 7;
  11.  
  12. template <typename T> T expo(T b, T e, const T &m) {if(e <= 1) return e==0?1: b;\
  13.   return (e&1) == 0?expo((b*b)%m, e>>1, m): (b*expo((b*b)%m, e>>1, m))%m; }
  14. template<typename T, typename S> T modinv(T a, S mod) { return expo(a, mod-2, mod); }
  15.  
  16. const int MAXN = 500;
  17. vector<LL> poly[10];
  18. LL fact[MAXN], ifact[MAXN];
  19.  
  20. void preprocess() {
  21.   fact[0] = (ifact[0] = 1);
  22.     for(int i = 1; i < MAXN; i++) {
  23.     fact[i] = (fact[i-1]*i)%mod;
  24.   }
  25.   ifact[MAXN-1] = modinv(fact[MAXN-1], mod); ifact[0] = 1;
  26.   for(LL i = MAXN-2; i > 0; i--){
  27.     ifact[i] = (ifact[i+1]*(i+1))%mod;
  28.   }
  29.   assert((fact[2]*ifact[2])%mod == 1);
  30. }
  31.  
  32. LL nCr(int n, int r) {
  33.   return (fact[n] * ((ifact[n-r] * ifact[r])%mod)) % mod;
  34. }
  35.  
  36. vector<LL> Mul(const vector<LL> &A, const vector<LL> &B) {
  37.   vector<LL> res(A.size() + B.size());
  38.   for(int i = 0; i < A.size(); i++) {
  39.     for(int j = 0; j < B.size(); j++) {
  40.       res[i + j] += A[i] * B[j] % mod;
  41.       if(res[i + j] >= mod) res[i + j] -= mod;
  42.     }
  43.   }
  44.   return res;
  45. }
  46.  
  47. class SumProduct {
  48. public:
  49.   int findSum(vector <int> amount, int blank1, int blank2) {
  50.     preprocess();
  51.     LL m = (expo(10ll, (LL)blank1, mod) - 1 + mod) % mod;
  52.     m = (m * ((expo(10ll, (LL)blank2, mod) - 1 + mod) % mod)) % mod;
  53.     m = m * modinv(9ll, mod) % mod;
  54.     m = m * modinv(9ll, mod) % mod;
  55.     cerr << "Mul = " << m << endl;
  56.     LL ans = 0;
  57.     for(LL d1 = 1; d1 < 10; d1++) {
  58.       if(amount[d1] == 0) continue;
  59.       for(LL d2 = 1; d2 < 10; d2++) {
  60.         if(amount[d2] == 0) continue;
  61.         amount[d1]--;
  62.         amount[d2]--;
  63.         if(amount[d1] >= 0 && amount[d2] >= 0) {
  64.           LL temp = m;
  65.           // if(d1 == d2) temp = temp * modinv(2ll, mod) % mod;
  66.           for(LL dgt = 0; dgt < 10; dgt++) {
  67.             poly[dgt].resize(amount[dgt] + 1);
  68.             for(LL i = 0; i < poly[dgt].size(); i++) {
  69.               poly[dgt][i] = ifact[i];
  70.             }
  71.           }
  72.           vector<LL> res = Mul(poly[0], poly[1]);
  73.           for(int dgt = 2; dgt < 10; dgt++) {
  74.             res = Mul(res, poly[dgt]);
  75.             res.resize(blank1 + blank2 + 2);
  76.           }
  77.           temp = temp * res[blank1 + blank2 - 2] % mod;
  78.           temp = temp * (d1 * d2) % mod;
  79.           temp = temp * fact[blank1 + blank2 - 2] % mod;
  80.           ans += temp;
  81.           ans %= mod;
  82.         }
  83.         amount[d1]++;
  84.         amount[d2]++;
  85.       }
  86.     }
  87.     return ans;
  88.   }
  89. };
  90.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/usr/bin/../lib/gcc/x86_64-linux-gnu/6.3.0/../../../x86_64-linux-gnu/crt1.o: In function `_start':
(.text+0x20): undefined reference to `main'
clang: error: linker command failed with exit code 1 (use -v to see invocation)
stdout
copy 
Standard output is empty
https://ideone.com/2TgWTZ
language:
C++14 (clang 8.0)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!