QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#115371#6157. 组合数问题HaccerKat100 ✓144ms7008kbC++2011.6kb2023-06-26 04:07:382023-06-26 04:07:39

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-26 04:07:39]
  • 评测
  • 测评结果:100
  • 用时:144ms
  • 内存:7008kb
  • [2023-06-26 04:07:38]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
template<typename T>
int SIZE(T (&t)){
    return t.size();
}

template<typename T, size_t N>
int SIZE(T (&t)[N]){
    return N;
}

string to_string(char t){
    return "'" + string({t}) + "'";
}

string to_string(bool t){
    return t ? "true" : "false";
}

string to_string(const string &t, int x1=0, int x2=1e9){
    string ret = "";
    for(int i = min(x1,SIZE(t)), _i = min(x2,SIZE(t)-1); i <= _i; ++i){
        ret += t[i];
    }
    return '"' + ret + '"';
}

string to_string(const char* t){
    string ret(t);
    return to_string(ret);
}

template<size_t N>
string to_string(const bitset<N> &t, int x1=0, int x2=1e9){
    string ret = "";
    for(int i = min(x1,SIZE(t)); i <= min(x2,SIZE(t)-1); ++i){
        ret += t[i] + '0';
    }
    return to_string(ret);
}

template<typename T, typename... Coords>
string to_string(const T (&t), int x1=0, int x2=1e9, Coords... C);

template<typename T, typename S>
string to_string(const pair<T, S> &t){
    return "(" + to_string(t.first) + ", " + to_string(t.second) + ")";
}

template<typename T, typename... Coords>
string to_string(const T (&t), int x1, int x2, Coords... C){
    string ret = "[";
    x1 = min(x1, SIZE(t));
    auto e = begin(t);
    advance(e,x1);
    for(int i = x1, _i = min(x2,SIZE(t)-1); i <= _i; ++i){
        ret += to_string(*e, C...) + (i != _i ? ", " : "");
        e = next(e);
    }
    return ret + "]";
}

template<int Index, typename... Ts>
struct print_tuple{
    string operator() (const tuple<Ts...>& t) {
        string ret = print_tuple<Index - 1, Ts...>{}(t);
        ret += (Index ? ", " : "");
        return ret + to_string(get<Index>(t));
    }
};

template<typename... Ts>
struct print_tuple<0, Ts...> {
    string operator() (const tuple<Ts...>& t) {
        return to_string(get<0>(t));
    }
};

template<typename... Ts>
string to_string(const tuple<Ts...>& t) {
    const auto Size = tuple_size<tuple<Ts...>>::value;
    return print_tuple<Size - 1, Ts...>{}(t);
}

void dbgr(){;}
template<typename Heads, typename... Tails>
void dbgr(Heads H, Tails... T){
    cout << to_string(H) << " | ";
    dbgr(T...);
}

void dbgs(){;}
template<typename Heads, typename... Tails>
void dbgs(Heads H, Tails... T){
    cout << H << " ";
    dbgs(T...);
}

/*
formatted functions:
*/

/*
consider __VA_ARGS__ as a whole:
dbgv() prints values only
dbg() prints name and values
*/
#define dbgv(...) cout << to_string(__VA_ARGS__) << endl;

#define dbg(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgv(__VA_ARGS__);
//#define dbg(...)

/*
consider __VA_ARGS__ as a sequence of arguments:
dbgr() prints values only
dbgm() prints names and values
*/
#define dbgr(...) dbgr(__VA_ARGS__); cout << endl;

#define dbgm(...) cout << "[" << #__VA_ARGS__ << "]: "; dbgr(__VA_ARGS__);

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

template <typename T>
T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a; swap(a, m);
    u -= t * v; swap(u, v);
  }
  assert(m == 1);
  return u;
}
 
template <typename T>
class Modular {
 public:
  using Type = typename decay<decltype(T::value)>::type;
 
  constexpr Modular() : value() {}
  template <typename U>
  Modular(const U& x) {
    value = normalize(x);
  }
 
  template <typename U>
  static Type normalize(const U& x) {
    Type v;
    if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
    else v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }
 
  const Type& operator()() const { return value; }
  template <typename U>
  explicit operator U() const { return static_cast<U>(value); }
  constexpr static Type mod() { return T::value; }
 
  Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
  Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
  template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
  template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
  Modular& operator++() { return *this += 1; }
  Modular& operator--() { return *this -= 1; }
  Modular operator++(int) { Modular result(*this); *this += 1; return result; }
  Modular operator--(int) { Modular result(*this); *this -= 1; return result; }
  Modular operator-() const { return Modular(-value); }
 
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
#ifdef _WIN32
    uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
    uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m;
    asm(
      "divl %4; \n\t"
      : "=a" (d), "=d" (m)
      : "d" (xh), "a" (xl), "r" (mod())
    );
    value = m;
#else
    value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
#endif
    return *this;
  }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, long long>::value, Modular>::type& operator*=(const Modular& rhs) {
    long long q = static_cast<long long>(static_cast<long double>(value) * rhs.value / mod());
    value = normalize(value * rhs.value - q * mod());
    return *this;
  }
  template <typename U = T>
  typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type& operator*=(const Modular& rhs) {
    value = normalize(value * rhs.value);
    return *this;
  }
 
  Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }
 
  friend const Type& abs(const Modular& x) { return x.value; }
 
  template <typename U>
  friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);
 
  template <typename U>
  friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);
 
  template <typename V, typename U>
  friend V& operator>>(V& stream, Modular<U>& number);
 
 private:
  Type value;
};
 
template <typename T> bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }
template <typename T, typename U> bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }
template <typename T, typename U> bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; }
 
template <typename T> bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
 
template <typename T> bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value < rhs.value; }
 
template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
 
template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
 
template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
 
template <typename T> Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
 
template<typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
  assert(b >= 0);
  Modular<T> x = a, res = 1;
  U p = b;
  while (p > 0) {
    if (p & 1) res *= x;
    x *= x;
    p >>= 1;
  }
  return res;
}
 
template <typename T>
bool IsZero(const Modular<T>& number) {
  return number() == 0;
}
 
template <typename T>
string to_string(const Modular<T>& number) {
  return to_string(number());
}
 
// U == std::ostream? but done this way because of fastoutput
template <typename U, typename T>
U& operator<<(U& stream, const Modular<T>& number) {
  return stream << number();
}
 
// U == std::istream? but done this way because of fastinput
template <typename U, typename T>
U& operator>>(U& stream, Modular<T>& number) {
  typename common_type<typename Modular<T>::Type, long long>::type x;
  stream >> x;
  number.value = Modular<T>::normalize(x);
  return stream;
}


using ModType = int;
 
struct VarMod { static ModType value; };
ModType VarMod::value;
ModType& md = VarMod::value;
using Mint = Modular<VarMod>;

 
// constexpr int md = (int) 1e9 + 7;
// using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
 
// vector<Mint> fact;
// vector<Mint> inv_fact;
 
// Mint C(int n, int k) {
//     if (k < 0 || k > n) {
//         return 0;
//     }

//     if (fact.empty()) {
//         fact.push_back(1);
//         inv_fact.push_back(1);
//     }

//     while ((int) fact.size() < n + 1) {
//         fact.push_back(fact.back() * (int) fact.size());
//         inv_fact.push_back(1 / fact.back());
//     }

//     return fact[n] * inv_fact[k] * inv_fact[n - k];
// }

typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
// using u128 = __uint128_t;
// using i128 = __int128;
const int mod = 1000000007;
const int N = 200005;
const int LOG = 20;
const int inf = 1e9;
const double eps = 1e-11;
string s;
int n, m, k, qq, x;
void solve() {
    cin >> n >> x >> md >> m;
    vector<Mint> a(m + 1);
    vector<vector<Mint>> f(m + 1, vector<Mint>(m + 1));
    for (int i = 0; i <= m; i++) {
        cin >> a[i];
        f[i][i] = 1;
    }
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == j) continue;
            f[i][j] = f[i - 1][j - 1] + j * f[i - 1][j];
        }    
    }
    
    Mint out = 0;
    for (int i = 0; i <= m; i++) {
        Mint cur = 1, curx = 1, curfact = 1;
        for (int j = 0; j <= i; j++) {
            out += a[i] * f[i][j] * curfact * curx * power((Mint)(x + 1), n - j);
            curfact *= (n - j), curx *= x;
        }
    }
    
    cout << out << "\n";
}

int32_t main() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

详细

Test #1:

score: 5
Accepted
time: 49ms
memory: 6940kb

input:

1000 643189585 831941236 1000
621444125 324708497 619770455 112615814 800909697 461794889 380815971 872773343 314541774 472606930 636420887 783552328 794270098 539204140 23007446 139105268 406306323 866123427 218553206 804461683 30473072 117201808 568299563 477252115 324883663 342559946 1371621 5042...

output:

692083420

result:

ok 1 number(s): "692083420"

Test #2:

score: 5
Accepted
time: 49ms
memory: 7000kb

input:

1000 503195138 513597392 1000
722484910 931359038 343065489 981840058 521519661 226445599 530176715 770414408 102322476 673203111 507109164 694874631 741867637 279337383 424160545 294330405 82544373 48857855 815232637 669279005 52910855 214526933 849319059 181639810 172299266 889272850 596357056 666...

output:

318265902

result:

ok 1 number(s): "318265902"

Test #3:

score: 5
Accepted
time: 48ms
memory: 6980kb

input:

1000 906011316 702916476 1000
426378198 448666835 928428034 473805142 373675324 45261623 502895126 736498316 231472510 191865836 242418084 544276235 444104055 477445639 356224464 953908838 306690394 584707561 294817458 752251380 852722174 469468566 503286490 871710527 705395858 404720545 938309838 1...

output:

186621654

result:

ok 1 number(s): "186621654"

Test #4:

score: 5
Accepted
time: 1ms
memory: 3404kb

input:

100000 677812091 277 0
807583683

output:

71

result:

ok 1 number(s): "71"

Test #5:

score: 5
Accepted
time: 1ms
memory: 3416kb

input:

100000 981163973 25889 0
973863137

output:

12731

result:

ok 1 number(s): "12731"

Test #6:

score: 5
Accepted
time: 0ms
memory: 3472kb

input:

100000 835568175 7401731 0
906329707

output:

3064835

result:

ok 1 number(s): "3064835"

Test #7:

score: 5
Accepted
time: 1ms
memory: 3408kb

input:

1000000000 790947092 627519428 0
60710186

output:

272191242

result:

ok 1 number(s): "272191242"

Test #8:

score: 5
Accepted
time: 1ms
memory: 3472kb

input:

1000000000 650690291 731646919 0
877581470

output:

15529275

result:

ok 1 number(s): "15529275"

Test #9:

score: 5
Accepted
time: 1ms
memory: 3468kb

input:

1000000000 797047750 618934290 3
961481438 877843421 701730260 298899

output:

420699238

result:

ok 1 number(s): "420699238"

Test #10:

score: 5
Accepted
time: 1ms
memory: 3472kb

input:

1000000000 864318301 584940599 3
633737140 774981490 625591778 241085537

output:

198331859

result:

ok 1 number(s): "198331859"

Test #11:

score: 5
Accepted
time: 0ms
memory: 3408kb

input:

1000000000 848364348 882312605 4
170103640 631151726 271592928 185866004 334973069

output:

52190000

result:

ok 1 number(s): "52190000"

Test #12:

score: 5
Accepted
time: 1ms
memory: 3420kb

input:

1000000000 632003439 731204527 5
528931262 239172080 749520006 43675943 695916953 6562492

output:

614687549

result:

ok 1 number(s): "614687549"

Test #13:

score: 5
Accepted
time: 126ms
memory: 6924kb

input:

1000000000 1 766455601 1000
558055814 109246028 38835513 947196933 242586123 147273834 256441677 15594213 98941360 755103145 463954471 169688646 98806912 642927659 621211739 713955885 391698389 163712447 588561728 647301220 39465644 800390415 324148500 871577287 613523228 342178732 36750461 26345791...

output:

657791066

result:

ok 1 number(s): "657791066"

Test #14:

score: 5
Accepted
time: 126ms
memory: 6952kb

input:

1000000000 1 873712850 1000
278171983 164635568 206054551 341466272 947345526 592513430 491563677 341146136 935528892 632574736 565810285 515879482 994979438 164263680 189449944 440718937 492084059 497263419 573679235 699086245 659495381 975774703 586571408 481989509 489369682 258500183 253174606 94...

output:

357599008

result:

ok 1 number(s): "357599008"

Test #15:

score: 5
Accepted
time: 130ms
memory: 7008kb

input:

1000000000 1 801809934 1000
326406661 169791972 761656767 15280008 186815446 186117411 265403224 308467755 392051233 725260841 341791121 418439521 777844152 419969954 730027819 343615863 568299464 475588222 277121423 761476244 202455418 960116443 484950749 866814884 28710946 434807477 996165424 7697...

output:

762344818

result:

ok 1 number(s): "762344818"

Test #16:

score: 5
Accepted
time: 130ms
memory: 6952kb

input:

1000000000 1 605325981 1000
300766868 885995664 277533356 168649814 892768488 291744630 646838712 856019873 59320837 572912057 690027481 880187770 374756433 903619161 122904149 844522459 95811969 772786363 239314288 992117811 387289152 145852010 767518940 830315681 766920764 440439657 93192393 76897...

output:

58895801

result:

ok 1 number(s): "58895801"

Test #17:

score: 5
Accepted
time: 144ms
memory: 6940kb

input:

1000000000 957733823 809081300 1000
533363221 638929575 443006622 286508611 691905309 228596664 175904171 410178708 451046889 127797916 415935615 570618723 800660185 563213999 903523847 668436995 933625911 861427774 755608174 362042286 314119712 895203661 417507948 153273866 167248092 956338547 3406...

output:

674756796

result:

ok 1 number(s): "674756796"

Test #18:

score: 5
Accepted
time: 141ms
memory: 6924kb

input:

1000000000 610363186 847371151 1000
665297781 786213968 431288588 909998294 800117192 27065236 692646918 881650665 265579161 44215444 99633849 582605709 402479473 972764887 466468004 538706661 251804078 454620935 67255325 783865759 693395798 583174943 305918899 503101381 981809034 107696 736321655 4...

output:

634262459

result:

ok 1 number(s): "634262459"

Test #19:

score: 5
Accepted
time: 141ms
memory: 6900kb

input:

1000000000 534756891 543527658 1000
702340808 598102723 853329752 572034620 975329351 617733109 230679944 829852779 503128018 355746866 443120420 51627950 127579068 106567561 79644532 703345646 306545813 302226744 726078059 118130342 68034745 998675817 12288173 368910305 490224052 374647055 27100878...

output:

149744150

result:

ok 1 number(s): "149744150"

Test #20:

score: 5
Accepted
time: 144ms
memory: 6904kb

input:

1000000000 909107105 657355356 1000
90722426 58432815 680303429 656802978 821714069 81032229 404049008 508394045 815033128 537356713 111806335 80898026 295991237 78868790 550351734 549534112 766404863 359634541 285022912 417815753 284604425 900505912 411877558 12589604 66352005 634143645 90909857 16...

output:

236596968

result:

ok 1 number(s): "236596968"

Extra Test:

score: 0
Extra Test Passed