fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define BI (bigint)
  4. //int n, k;
  5.  
  6. const int base = 1000000000; const int base_digits = 9;
  7. struct bigint {
  8.     vector<int> a; int sign;
  9.  
  10.     bigint() :
  11.         sign(1) {
  12.     }
  13.  
  14.     bigint(long long v) {
  15.         *this = v;
  16.     }
  17.  
  18.     bigint(const string &s) {
  19.         read(s);
  20.     }
  21.  
  22.     void operator=(const bigint &v) {
  23.         sign = v.sign;
  24.         a = v.a;
  25.     }
  26.  
  27.     void operator=(long long v) {
  28.         sign = 1;
  29.         if (v < 0)
  30.             sign = -1, v = -v;
  31.         for (; v > 0; v = v / base)
  32.             a.push_back(v % base);
  33.     }
  34.  
  35.     bigint operator+(const bigint &v) const {
  36.         if (sign == v.sign) {
  37.             bigint res = v;
  38.  
  39.             for (int i = 0, carry = 0; i < (int) max(a.size(), v.a.size()) || carry; ++i) {
  40.                 if (i == (int) res.a.size())
  41.                     res.a.push_back(0);
  42.                 res.a[i] += carry + (i < (int) a.size() ? a[i] : 0);
  43.                 carry = res.a[i] >= base;
  44.                 if (carry)
  45.                     res.a[i] -= base;
  46.             }
  47.             return res;
  48.         }
  49.         return *this - (-v);
  50.     }
  51.  
  52.     bigint operator-(const bigint &v) const {
  53.         if (sign == v.sign) {
  54.             if (abs() >= v.abs()) {
  55.                 bigint res = *this;
  56.                 for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i) {
  57.                     res.a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0);
  58.                     carry = res.a[i] < 0;
  59.                     if (carry)
  60.                         res.a[i] += base;
  61.                 }
  62.                 res.trim();
  63.                 return res;
  64.             }
  65.             return -(v - *this);
  66.         }
  67.         return *this + (-v);
  68.     }
  69.  
  70.     void operator*=(int v) {
  71.         if (v < 0)
  72.             sign = -sign, v = -v;
  73.         for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i) {
  74.             if (i == (int) a.size())
  75.                 a.push_back(0);
  76.             long long cur = a[i] * (long long) v + carry;
  77.             carry = (int) (cur / base);
  78.             a[i] = (int) (cur % base);
  79.             //asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
  80.         }
  81.         trim();
  82.     }
  83.  
  84.     bigint operator*(int v) const {
  85.         bigint res = *this;
  86.         res *= v;
  87.         return res;
  88.     }
  89.  
  90.     friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1) {
  91.         int norm = base / (b1.a.back() + 1);
  92.         bigint a = a1.abs() * norm;
  93.         bigint b = b1.abs() * norm;
  94.         bigint q, r;
  95.         q.a.resize(a.a.size());
  96.  
  97.         for (int i = a.a.size() - 1; i >= 0; i--) {
  98.             r *= base;
  99.             r += a.a[i];
  100.             int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
  101.             int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
  102.             int d = ((long long) base * s1 + s2) / b.a.back();
  103.             r -= b * d;
  104.             while (r < 0)
  105.                 r += b, --d;
  106.             q.a[i] = d;
  107.         }
  108.  
  109.         q.sign = a1.sign * b1.sign;
  110.         r.sign = a1.sign;
  111.         q.trim();
  112.         r.trim();
  113.         return make_pair(q, r / norm);
  114.     }
  115.  
  116.     bigint operator/(const bigint &v) const {
  117.         return divmod(*this, v).first;
  118.     }
  119.  
  120.     bigint operator%(const bigint &v) const {
  121.         return divmod(*this, v).second;
  122.     }
  123.  
  124.     void operator/=(int v) {
  125.         if (v < 0)
  126.             sign = -sign, v = -v;
  127.         for (int i = (int) a.size() - 1, rem = 0; i >= 0; --i) {
  128.             long long cur = a[i] + rem * (long long) base;
  129.             a[i] = (int) (cur / v);
  130.             rem = (int) (cur % v);
  131.         }
  132.         trim();
  133.     }
  134.  
  135.     bigint operator/(int v) const {
  136.         bigint res = *this;
  137.         res /= v;
  138.         return res;
  139.     }
  140.  
  141.     int operator%(int v) const {
  142.         if (v < 0)
  143.             v = -v;
  144.         int m = 0;
  145.         for (int i = a.size() - 1; i >= 0; --i)
  146.             m = (a[i] + m * (long long) base) % v;
  147.         return m * sign;
  148.     }
  149.  
  150.     void operator+=(const bigint &v) {
  151.         *this = *this + v;
  152.     }
  153.     void operator-=(const bigint &v) {
  154.         *this = *this - v;
  155.     }
  156.     void operator*=(const bigint &v) {
  157.         *this = *this * v;
  158.     }
  159.     void operator/=(const bigint &v) {
  160.         *this = *this / v;
  161.     }
  162.  
  163.     bool operator<(const bigint &v) const {
  164.         if (sign != v.sign)
  165.             return sign < v.sign;
  166.         if (a.size() != v.a.size())
  167.             return a.size() * sign < v.a.size() * v.sign;
  168.         for (int i = a.size() - 1; i >= 0; i--)
  169.             if (a[i] != v.a[i])
  170.                 return a[i] * sign < v.a[i] * sign;
  171.         return false;
  172.     }
  173.  
  174.     bool operator>(const bigint &v) const {
  175.         return v < *this;
  176.     }
  177.     bool operator<=(const bigint &v) const {
  178.         return !(v < *this);
  179.     }
  180.     bool operator>=(const bigint &v) const {
  181.         return !(*this < v);
  182.     }
  183.     bool operator==(const bigint &v) const {
  184.         return !(*this < v) && !(v < *this);
  185.     }
  186.     bool operator!=(const bigint &v) const {
  187.         return *this < v || v < *this;
  188.     }
  189.  
  190.     void trim() {
  191.         while (!a.empty() && !a.back())
  192.             a.pop_back();
  193.         if (a.empty())
  194.             sign = 1;
  195.     }
  196.  
  197.     bool isZero() const {
  198.         return a.empty() || (a.size() == 1 && !a[0]);
  199.     }
  200.  
  201.     bigint operator-() const {
  202.         bigint res = *this;
  203.         res.sign = -sign;
  204.         return res;
  205.     }
  206.  
  207.     bigint abs() const {
  208.         bigint res = *this;
  209.         res.sign *= res.sign;
  210.         return res;
  211.     }
  212.  
  213.     long long longValue() const {
  214.         long long res = 0;
  215.         for (int i = a.size() - 1; i >= 0; i--)
  216.             res = res * base + a[i];
  217.         return res * sign;
  218.     }
  219.  
  220. //    friend bigint gcd(const bigint &a, const bigint &b) {
  221. //        return b.isZero() ? a : gcd(b, a % b);
  222. //    }
  223. //    friend bigint lcm(const bigint &a, const bigint &b) {
  224. //        return a / gcd(a, b) * b;
  225. //    }
  226.  
  227.     void read(const string &s) {
  228.         sign = 1;
  229.         a.clear();
  230.         int pos = 0;
  231.         while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {
  232.             if (s[pos] == '-')
  233.                 sign = -sign;
  234.             ++pos;
  235.         }
  236.         for (int i = s.size() - 1; i >= pos; i -= base_digits) {
  237.             int x = 0;
  238.             for (int j = max(pos, i - base_digits + 1); j <= i; j++)
  239.                 x = x * 10 + s[j] - '0';
  240.             a.push_back(x);
  241.         }
  242.         trim();
  243.     }
  244.  
  245.     friend istream& operator>>(istream &stream, bigint &v) {
  246.         string s;
  247.         stream >> s;
  248.         v.read(s);
  249.         return stream;
  250.     }
  251.  
  252.     friend ostream& operator<<(ostream &stream, const bigint &v) {
  253.         if (v.sign == -1)
  254.             stream << '-';
  255.         stream << (v.a.empty() ? 0 : v.a.back());
  256.         for (int i = (int) v.a.size() - 2; i >= 0; --i)
  257.             stream << setw(base_digits) << setfill('0') << v.a[i];
  258.         return stream;
  259.     }
  260.  
  261.     static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
  262.         vector<long long> p(max(old_digits, new_digits) + 1);
  263.         p[0] = 1;
  264.         for (int i = 1; i < (int) p.size(); i++)
  265.             p[i] = p[i - 1] * 10;
  266.         vector<int> res;
  267.         long long cur = 0;
  268.         int cur_digits = 0;
  269.         for (int i = 0; i < (int) a.size(); i++) {
  270.             cur += a[i] * p[cur_digits];
  271.             cur_digits += old_digits;
  272.             while (cur_digits >= new_digits) {
  273.                 res.push_back(int(cur % p[new_digits]));
  274.                 cur /= p[new_digits];
  275.                 cur_digits -= new_digits;
  276.             }
  277.         }
  278.         res.push_back((int) cur);
  279.         while (!res.empty() && !res.back())
  280.             res.pop_back();
  281.         return res;
  282.     }
  283.  
  284.     typedef vector<long long> vll;
  285.  
  286.     static vll karatsubaMultiply(const vll &a, const vll &b) {
  287.         int n = a.size();
  288.         vll res(n + n);
  289.         if (n <= 32) {
  290.             for (int i = 0; i < n; i++)
  291.                 for (int j = 0; j < n; j++)
  292.                     res[i + j] += a[i] * b[j];
  293.             return res;
  294.         }
  295.  
  296.         int k = n >> 1;
  297.         vll a1(a.begin(), a.begin() + k);
  298.         vll a2(a.begin() + k, a.end());
  299.         vll b1(b.begin(), b.begin() + k);
  300.         vll b2(b.begin() + k, b.end());
  301.  
  302.         vll a1b1 = karatsubaMultiply(a1, b1);
  303.         vll a2b2 = karatsubaMultiply(a2, b2);
  304.  
  305.         for (int i = 0; i < k; i++)
  306.             a2[i] += a1[i];
  307.         for (int i = 0; i < k; i++)
  308.             b2[i] += b1[i];
  309.  
  310.         vll r = karatsubaMultiply(a2, b2);
  311.         for (int i = 0; i < (int) a1b1.size(); i++)
  312.             r[i] -= a1b1[i];
  313.         for (int i = 0; i < (int) a2b2.size(); i++)
  314.             r[i] -= a2b2[i];
  315.  
  316.         for (int i = 0; i < (int) r.size(); i++)
  317.             res[i + k] += r[i];
  318.         for (int i = 0; i < (int) a1b1.size(); i++)
  319.             res[i] += a1b1[i];
  320.         for (int i = 0; i < (int) a2b2.size(); i++)
  321.             res[i + n] += a2b2[i];
  322.         return res;
  323.     }
  324.  
  325.     bigint operator*(const bigint &v) const {
  326.         vector<int> a6 = convert_base(this->a, base_digits, 6);
  327.         vector<int> b6 = convert_base(v.a, base_digits, 6);
  328.         vll a(a6.begin(), a6.end());
  329.         vll b(b6.begin(), b6.end());
  330.         while (a.size() < b.size())
  331.             a.push_back(0);
  332.         while (b.size() < a.size())
  333.             b.push_back(0);
  334.         while (a.size() & (a.size() - 1))
  335.             a.push_back(0), b.push_back(0);
  336.         vll c = karatsubaMultiply(a, b);
  337.         bigint res;
  338.         res.sign = sign * v.sign;
  339.         for (int i = 0, carry = 0; i < (int) c.size(); i++) {
  340.             long long cur = c[i] + carry;
  341.             res.a.push_back((int) (cur % 1000000));
  342.             carry = (int) (cur / 1000000);
  343.         }
  344.         res.a = convert_base(res.a, 6, base_digits);
  345.         res.trim();
  346.         return res;
  347.     }
  348. };
  349.  
  350.  
  351. bigint mul(bigint a, int b)
  352. {
  353.     bigint res = 1;
  354.     for(int i = 1; i<=b; i++)
  355.         res *= a;
  356.     return res;
  357. }
  358.  
  359.  
  360. int main()
  361. {
  362.     int k;
  363. 	bigint n;
  364.     cin>>n>>k;
  365.     if(k == 1) cout<<n * (n + BI 1) / 2;
  366.     if(k == 2) cout<<n * (n + BI 1) * (BI 2 * n + BI 1) / 6;
  367.     if(k == 3) cout<<mul(n, 2) * mul((n + BI 1), 2) / 4;
  368.     if(k == 4) cout<<n * (n + BI 1) * (BI 2*n + BI 1) * (BI 3 * mul(n, 2) + BI 3 * n  - BI 1) / 30;
  369.     if(k == 5) cout<<mul(n, 2) * (BI 2 * mul(n, 2) + BI 2 * n - BI 1) * mul(n + 1, 2) / 12;
  370.     if(k == 6) cout<<n * (n + BI 1) * (BI 2 * n + BI 1) * (BI 3 * mul(n, 4) + BI 6 * mul(n, 3) - BI 3 * n + BI 1) / 42;
  371.     if(k == 7) cout<<mul(n, 2) * (BI 3 * mul(n, 4) + BI 6 * mul(n, 3) - mul(n, 2) - BI 4 * n + BI 2) * mul(n+1, 2) / 24;
  372.     if(k == 8) cout<<n * (n + BI 1) * (BI 2 * n + BI 1) * (BI 5 * mul(n, 6) + BI 15 * mul(n, 5) + BI 5 * mul(n, 4) - BI 15 * mul(n, 3) - mul(n, 2) + BI 9 * n - BI 3) / 90;
  373.     if(k == 9) cout<<mul(n, 2) * (mul(n, 2) + n - BI 1) * (BI 2 * mul(n, 4) + BI 4 * mul(n, 3) - mul(n, 2) - BI 3 * n + BI 3) * mul(n + 1, 2) / 20;
  374.     if(k == 10) cout<<n * (n + BI 1) * (BI 2 * n + BI 1) * (mul(n, 2) + n - BI 1) * (BI 3 * mul(n, 6) + BI 9 * mul(n, 5) + BI 2 * mul(n, 4) - BI 11 * mul(n, 3) + BI 3 * mul(n, 2) + BI 10 * n - BI 5) / 66;
  375.     if(k > 10)
  376.     {
  377.         bigint ans;
  378.         for (bigint i = BI 1; i <= BI n; i+=1)
  379.         {
  380.             bigint tmp = mul(i, k);
  381.             ans += tmp;
  382.         }
  383.     cout << ans;
  384.     }
  385. }
Success #stdin #stdout 0.03s 5404KB
comments (?)
stdin
copy 
100 100
stdout
copy 
157211406637054876047170714793672086843814311171382380612596108831201947669658622317126645748904454905428999917816240712232510830329707275257029895123985909786290997404450073406292199564392363955731330
https://ideone.com/9jbNTq
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
public

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!