fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define ii pair<int,int>
  5. #define c_bit(i) __builtin_popcountll(i)
  6. #define Bit(mask,i) (((mask)>>(i)) & 1)
  7. #define onbit(mask,i) ((mask)| (1LL << (i)))
  8. #define offbit(mask,i)((mask) &~ (1LL <<(i)))
  9. using namespace std;
  10. const int MAXN=1e3+10;
  11. const int mod=1e9+7;
  12. const int base = 1000000000;
  13. const int base_digits = 9;
  14. struct bigint {
  15.     vector<int> a;
  16.     int sign;
  17.     /*<arpa>*/
  18.     int size(){
  19.         if(a.empty())return 0;
  20.         int ans=(a.size()-1)*base_digits;
  21.         int ca=a.back();
  22.         while(ca)
  23.             ans++,ca/=10;
  24.         return ans;
  25.     }
  26.     bigint operator ^(const bigint &v){
  27.         bigint ans=1,a=*this,b=v;
  28.         while(!b.isZero()){
  29.             if(b%2)
  30.                 ans*=a;
  31.             a*=a,b/=2;
  32.         }
  33.         return ans;
  34.     }
  35.     string to_string(){
  36.         stringstream ss;
  37.         ss << *this;
  38.         string s;
  39.         ss >> s;
  40.         return s;
  41.     }
  42.     int sumof(){
  43.         string s = to_string();
  44.         int ans = 0;
  45.         for(auto c : s)  ans += c - '0';
  46.         return ans;
  47.     }
  48.     /*</arpa>*/
  49.     bigint() :
  50.         sign(1) {
  51.     }
  52.  
  53.     bigint(long long v) {
  54.         *this = v;
  55.     }
  56.  
  57.     bigint(const string &s) {
  58.         read(s);
  59.     }
  60.  
  61.     void operator=(const bigint &v) {
  62.         sign = v.sign;
  63.         a = v.a;
  64.     }
  65.  
  66.     void operator=(long long v) {
  67.         sign = 1;
  68.         a.clear();
  69.         if (v < 0)
  70.             sign = -1, v = -v;
  71.         for (; v > 0; v = v / base)
  72.             a.push_back(v % base);
  73.     }
  74.  
  75.     bigint operator+(const bigint &v) const {
  76.         if (sign == v.sign) {
  77.             bigint res = v;
  78.  
  79.             for (int i = 0, carry = 0; i < (int) max(a.size(), v.a.size()) or carry; ++i) {
  80.                 if (i == (int) res.a.size())
  81.                     res.a.push_back(0);
  82.                 res.a[i] += carry + (i < (int) a.size() ? a[i] : 0);
  83.                 carry = res.a[i] >= base;
  84.                 if (carry)
  85.                     res.a[i] -= base;
  86.             }
  87.             return res;
  88.         }
  89.         return *this - (-v);
  90.     }
  91.  
  92.     bigint operator-(const bigint &v) const {
  93.         if (sign == v.sign) {
  94.             if (abs() >= v.abs()) {
  95.                 bigint res = *this;
  96.                 for (int i = 0, carry = 0; i < (int) v.a.size() or carry; ++i) {
  97.                     res.a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0);
  98.                     carry = res.a[i] < 0;
  99.                     if (carry)
  100.                         res.a[i] += base;
  101.                 }
  102.                 res.trim();
  103.                 return res;
  104.             }
  105.             return -(v - *this);
  106.         }
  107.         return *this + (-v);
  108.     }
  109.  
  110.     void operator*=(int v) {
  111.         if (v < 0)
  112.             sign = -sign, v = -v;
  113.         for (int i = 0, carry = 0; i < (int) a.size() or carry; ++i) {
  114.             if (i == (int) a.size())
  115.                 a.push_back(0);
  116.             long long cur = a[i] * (long long) v + carry;
  117.             carry = (int) (cur / base);
  118.             a[i] = (int) (cur % base);
  119.             //asm("divl %ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
  120.         }
  121.         trim();
  122.     }
  123.  
  124.     bigint operator*(int v) const {
  125.         bigint res = *this;
  126.         res *= v;
  127.         return res;
  128.     }
  129.  
  130.     void operator*=(long long v) {
  131.         if (v < 0)
  132.             sign = -sign, v = -v;
  133.         if(v > base){
  134.             *this = *this * (v / base) * base + *this * (v % base);
  135.             return ;
  136.         }
  137.         for (int i = 0, carry = 0; i < (int) a.size() or carry; ++i) {
  138.             if (i == (int) a.size())
  139.                 a.push_back(0);
  140.             long long cur = a[i] * (long long) v + carry;
  141.             carry = (int) (cur / base);
  142.             a[i] = (int) (cur % base);
  143.             //asm("divl %ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
  144.         }
  145.         trim();
  146.     }
  147.  
  148.     bigint operator*(long long v) const {
  149.         bigint res = *this;
  150.         res *= v;
  151.         return res;
  152.     }
  153.  
  154.     friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1) {
  155.         int norm = base / (b1.a.back() + 1);
  156.         bigint a = a1.abs() * norm;
  157.         bigint b = b1.abs() * norm;
  158.         bigint q, r;
  159.         q.a.resize(a.a.size());
  160.  
  161.         for (int i = a.a.size() - 1; i >= 0; i--) {
  162.             r *= base;
  163.             r += a.a[i];
  164.             int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
  165.             int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
  166.             int d = ((long long) base * s1 + s2) / b.a.back();
  167.             r -= b * d;
  168.             while (r < 0)
  169.                 r += b, --d;
  170.             q.a[i] = d;
  171.         }
  172.  
  173.         q.sign = a1.sign * b1.sign;
  174.         r.sign = a1.sign;
  175.         q.trim();
  176.         r.trim();
  177.         return make_pair(q, r / norm);
  178.     }
  179.  
  180.     bigint operator/(const bigint &v) const {
  181.         return divmod(*this, v).first;
  182.     }
  183.  
  184.     bigint operator%(const bigint &v) const {
  185.         return divmod(*this, v).second;
  186.     }
  187.  
  188.     void operator/=(int v) {
  189.         if (v < 0)
  190.             sign = -sign, v = -v;
  191.         for (int i = (int) a.size() - 1, rem = 0; i >= 0; --i) {
  192.             long long cur = a[i] + rem * (long long) base;
  193.             a[i] = (int) (cur / v);
  194.             rem = (int) (cur % v);
  195.         }
  196.         trim();
  197.     }
  198.  
  199.     bigint operator/(int v) const {
  200.         bigint res = *this;
  201.         res /= v;
  202.         return res;
  203.     }
  204.  
  205.     int operator%(int v) const {
  206.         if (v < 0)
  207.             v = -v;
  208.         int m = 0;
  209.         for (int i = a.size() - 1; i >= 0; --i)
  210.             m = (a[i] + m * (long long) base) % v;
  211.         return m * sign;
  212.     }
  213.  
  214.     void operator+=(const bigint &v) {
  215.         *this = *this + v;
  216.     }
  217.     void operator-=(const bigint &v) {
  218.         *this = *this - v;
  219.     }
  220.     void operator*=(const bigint &v) {
  221.         *this = *this * v;
  222.     }
  223.     void operator/=(const bigint &v) {
  224.         *this = *this / v;
  225.     }
  226.  
  227.     bool operator<(const bigint &v) const {
  228.         if (sign != v.sign)
  229.             return sign < v.sign;
  230.         if (a.size() != v.a.size())
  231.             return a.size() * sign < v.a.size() * v.sign;
  232.         for (int i = a.size() - 1; i >= 0; i--)
  233.             if (a[i] != v.a[i])
  234.                 return a[i] * sign < v.a[i] * sign;
  235.         return false;
  236.     }
  237.  
  238.     bool operator>(const bigint &v) const {
  239.         return v < *this;
  240.     }
  241.     bool operator<=(const bigint &v) const {
  242.         return !(v < *this);
  243.     }
  244.     bool operator>=(const bigint &v) const {
  245.         return !(*this < v);
  246.     }
  247.     bool operator==(const bigint &v) const {
  248.         return !(*this < v) && !(v < *this);
  249.     }
  250.     bool operator!=(const bigint &v) const {
  251.         return *this < v or v < *this;
  252.     }
  253.  
  254.     void trim() {
  255.         while (!a.empty() && !a.back())
  256.             a.pop_back();
  257.         if (a.empty())
  258.             sign = 1;
  259.     }
  260.  
  261.     bool isZero() const {
  262.         return a.empty() or (a.size() == 1 && !a[0]);
  263.     }
  264.  
  265.     bigint operator-() const {
  266.         bigint res = *this;
  267.         res.sign = -sign;
  268.         return res;
  269.     }
  270.  
  271.     bigint abs() const {
  272.         bigint res = *this;
  273.         res.sign *= res.sign;
  274.         return res;
  275.     }
  276.  
  277.     long long longValue() const {
  278.         long long res = 0;
  279.         for (int i = a.size() - 1; i >= 0; i--)
  280.             res = res * base + a[i];
  281.         return res * sign;
  282.     }
  283.  
  284.     friend bigint gcd(const bigint &a, const bigint &b) {
  285.         return b.isZero() ? a : gcd(b, a % b);
  286.     }
  287.     friend bigint lcm(const bigint &a, const bigint &b) {
  288.         return a / gcd(a, b) * b;
  289.     }
  290.  
  291.     void read(const string &s) {
  292.         sign = 1;
  293.         a.clear();
  294.         int pos = 0;
  295.         while (pos < (int) s.size() && (s[pos] == '-' or s[pos] == '+')) {
  296.             if (s[pos] == '-')
  297.                 sign = -sign;
  298.             ++pos;
  299.         }
  300.         for (int i = s.size() - 1; i >= pos; i -= base_digits) {
  301.             int x = 0;
  302.             for (int j = max(pos, i - base_digits + 1); j <= i; j++)
  303.                 x = x * 10 + s[j] - '0';
  304.             a.push_back(x);
  305.         }
  306.         trim();
  307.     }
  308.  
  309.     friend istream& operator>>(istream &stream, bigint &v) {
  310.         string s;
  311.         stream >> s;
  312.         v.read(s);
  313.         return stream;
  314.     }
  315.  
  316.     friend ostream& operator<<(ostream &stream, const bigint &v) {
  317.         if (v.sign == -1)
  318.             stream << '-';
  319.         stream << (v.a.empty() ? 0 : v.a.back());
  320.         for (int i = (int) v.a.size() - 2; i >= 0; --i)
  321.             stream << setw(base_digits) << setfill('0') << v.a[i];
  322.         return stream;
  323.     }
  324.  
  325.     static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
  326.         vector<long long> p(max(old_digits, new_digits) + 1);
  327.         p[0] = 1;
  328.         for (int i = 1; i < (int) p.size(); i++)
  329.             p[i] = p[i - 1] * 10;
  330.         vector<int> res;
  331.         long long cur = 0;
  332.         int cur_digits = 0;
  333.         for (int i = 0; i < (int) a.size(); i++) {
  334.             cur += a[i] * p[cur_digits];
  335.             cur_digits += old_digits;
  336.             while (cur_digits >= new_digits) {
  337.                 res.push_back(int(cur % p[new_digits]));
  338.                 cur /= p[new_digits];
  339.                 cur_digits -= new_digits;
  340.             }
  341.         }
  342.         res.push_back((int) cur);
  343.         while (!res.empty() && !res.back())
  344.             res.pop_back();
  345.         return res;
  346.     }
  347.  
  348.     typedef vector<long long> vll;
  349.  
  350.     static vll karatsubaMultiply(const vll &a, const vll &b) {
  351.         int n = a.size();
  352.         vll res(n + n);
  353.         if (n <= 32) {
  354.             for (int i = 0; i < n; i++)
  355.                 for (int j = 0; j < n; j++)
  356.                     res[i + j] += a[i] * b[j];
  357.             return res;
  358.         }
  359.  
  360.         int k = n >> 1;
  361.         vll a1(a.begin(), a.begin() + k);
  362.         vll a2(a.begin() + k, a.end());
  363.         vll b1(b.begin(), b.begin() + k);
  364.         vll b2(b.begin() + k, b.end());
  365.  
  366.         vll a1b1 = karatsubaMultiply(a1, b1);
  367.         vll a2b2 = karatsubaMultiply(a2, b2);
  368.  
  369.         for (int i = 0; i < k; i++)
  370.             a2[i] += a1[i];
  371.         for (int i = 0; i < k; i++)
  372.             b2[i] += b1[i];
  373.  
  374.         vll r = karatsubaMultiply(a2, b2);
  375.         for (int i = 0; i < (int) a1b1.size(); i++)
  376.             r[i] -= a1b1[i];
  377.         for (int i = 0; i < (int) a2b2.size(); i++)
  378.             r[i] -= a2b2[i];
  379.  
  380.         for (int i = 0; i < (int) r.size(); i++)
  381.             res[i + k] += r[i];
  382.         for (int i = 0; i < (int) a1b1.size(); i++)
  383.             res[i] += a1b1[i];
  384.         for (int i = 0; i < (int) a2b2.size(); i++)
  385.             res[i + n] += a2b2[i];
  386.         return res;
  387.     }
  388.  
  389.     bigint operator*(const bigint &v) const {
  390.         vector<int> a6 = convert_base(this->a, base_digits, 6);
  391.         vector<int> b6 = convert_base(v.a, base_digits, 6);
  392.         vll a(a6.begin(), a6.end());
  393.         vll b(b6.begin(), b6.end());
  394.         while (a.size() < b.size())
  395.             a.push_back(0);
  396.         while (b.size() < a.size())
  397.             b.push_back(0);
  398.         while (a.size() & (a.size() - 1))
  399.             a.push_back(0), b.push_back(0);
  400.         vll c = karatsubaMultiply(a, b);
  401.         bigint res;
  402.         res.sign = sign * v.sign;
  403.         for (int i = 0, carry = 0; i < (int) c.size(); i++) {
  404.             long long cur = c[i] + carry;
  405.             res.a.push_back((int) (cur % 1000000));
  406.             carry = (int) (cur / 1000000);
  407.         }
  408.         res.a = convert_base(res.a, 6, base_digits);
  409.         res.trim();
  410.         return res;
  411.     }
  412. };
  413. int n,kmod;
  414. bigint dp[3*MAXN][MAXN][2][2]; int pre[3*MAXN];
  415. bigint dequ(int id,int M,int ok1,int ok2){
  416.     if(id > n) return ok1 && ok2 && !M;
  417.     if(dp[id][M][ok1][ok2] != -1) return dp[id][M][ok1][ok2];
  418.     bigint ans = 0;
  419.     for(int i = 0 ; i < 2 ; i ++){
  420.         for(int j = 0 ; j < 2 ; j ++){
  421.             for(int k = 0 ; k < 2 ; k ++){
  422.                 if((!ok1 && j < i) || (!ok2 && k < j)) continue;
  423.                 int m = (M + (i + j + k) * pre[n - id] * (id/3+1)) % kmod;
  424.                 ans += dequ(id + 1,m,ok1 || j > i,ok2 || k > j) ;
  425.             }
  426.         }
  427.     }
  428.     dp[id][M][ok1][ok2] = ans;
  429.     return dp[id][M][ok1][ok2];
  430. }
  431. int main()
  432. {
  433.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  434. //    freopen("BEAUTIFUN.inp","r",stdin);
  435. //    freopen("BEAUTIFUN.out","w",stdout);
  436.     cin >> n >> kmod; n = n * 3 - 1;
  437.     if(n == 0 || kmod == 0) return 0;
  438.     pre[0] = 1,pre[1] = 2,pre[2] = 4;
  439.     for(int i = 3 ; i < n ; i += 3) {
  440.         pre[i] = (pre[i-3] * 10 + 1) % kmod;
  441.         pre[i+1] = (pre[i-2] * 10 + 2) % kmod;
  442.         pre[i+2] = (pre[i-1] * 10 + 4) %kmod;
  443.     }
  444.     for(int i = 0; i < MAXN * 3; ++ i) for(int j = 0; j < MAXN; ++ j) for(int k = 0; k < 1; ++ k) for(int l = 0; l < 1; ++ l)
  445.     	dp[i][j][k][l] = -1;
  446.     bigint ans = 0;
  447.     for(int i = 1 ; i <= 7 ; i ++){
  448.         for(int j = i ; j <= 7 ; j ++){
  449.             for(int k = j ; k <= 7 ; k ++){
  450.                 int ok1 = j > i;
  451.                 int ok2 = k > j;
  452.                 int m = ((i + j + k) * pre[n-2]) % kmod;
  453.                 ans = ( ans + dequ(3,m,ok1,ok2) ) % mod;
  454.             }
  455.         }
  456.     }
  457.     cout << ans;
  458.         cerr << "\nTime elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s.\n";
  459.     return 0;
  460. }
Success #stdin #stdout 0.09s 386272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/6Ismta
language:
C++14 (gcc 8.3)
created:
8 days 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!