QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #879414 | #9697. Algebra | ucup-team987# | AC ✓ | 1630ms | 4608kb | C++20 | 15.5kb | 2025-02-02 01:36:15 | 2025-02-02 01:36:16 |
Judging History
answer
#include<iostream>
#include<vector>
#include<cassert>
#include <cassert>
#include <numeric>
#include <type_traits>
#ifdef _MSC_VER
#include <intrin.h>
#endif
#include <utility>
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace atcoder {
namespace internal {
constexpr long long safe_mod(long long x, long long m) {
x %= m;
if (x < 0) x += m;
return x;
}
struct barrett {
unsigned int _m;
unsigned long long im;
explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
unsigned int umod() const { return _m; }
unsigned int mul(unsigned int a, unsigned int b) const {
unsigned long long z = a;
z *= b;
#ifdef _MSC_VER
unsigned long long x;
_umul128(z, im, &x);
#else
unsigned long long x =
(unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
unsigned int v = (unsigned int)(z - x * _m);
if (_m <= v) v += _m;
return v;
}
};
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
if (m == 1) return 0;
unsigned int _m = (unsigned int)(m);
unsigned long long r = 1;
unsigned long long y = safe_mod(x, m);
while (n) {
if (n & 1) r = (r * y) % _m;
y = (y * y) % _m;
n >>= 1;
}
return r;
}
constexpr bool is_prime_constexpr(int n) {
if (n <= 1) return false;
if (n == 2 || n == 7 || n == 61) return true;
if (n % 2 == 0) return false;
long long d = n - 1;
while (d % 2 == 0) d /= 2;
constexpr long long bases[3] = {2, 7, 61};
for (long long a : bases) {
long long t = d;
long long y = pow_mod_constexpr(a, t, n);
while (t != n - 1 && y != 1 && y != n - 1) {
y = y * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0) {
return false;
}
}
return true;
}
template <int n> constexpr bool is_prime = is_prime_constexpr(n);
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
a = safe_mod(a, b);
if (a == 0) return {b, 0};
long long s = b, t = a;
long long m0 = 0, m1 = 1;
while (t) {
long long u = s / t;
s -= t * u;
m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
if (m0 < 0) m0 += b / s;
return {s, m0};
}
constexpr int primitive_root_constexpr(int m) {
if (m == 2) return 1;
if (m == 167772161) return 3;
if (m == 469762049) return 3;
if (m == 754974721) return 11;
if (m == 998244353) return 3;
int divs[20] = {};
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; (long long)(i)*i <= x; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) {
divs[cnt++] = x;
}
for (int g = 2;; g++) {
bool ok = true;
for (int i = 0; i < cnt; i++) {
if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
template <int m> constexpr int primitive_root = primitive_root_constexpr(m);
unsigned long long floor_sum_unsigned(unsigned long long n,
unsigned long long m,
unsigned long long a,
unsigned long long b) {
unsigned long long ans = 0;
while (true) {
if (a >= m) {
ans += n * (n - 1) / 2 * (a / m);
a %= m;
}
if (b >= m) {
ans += n * (b / m);
b %= m;
}
unsigned long long y_max = a * n + b;
if (y_max < m) break;
n = (unsigned long long)(y_max / m);
b = (unsigned long long)(y_max % m);
std::swap(m, a);
}
return ans;
}
} // namespace internal
} // namespace atcoder
#include <cassert>
#include <numeric>
#include <type_traits>
namespace atcoder {
namespace internal {
#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value ||
std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value ||
std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value,
__uint128_t,
unsigned __int128>;
template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
is_signed_int128<T>::value ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
std::is_signed<T>::value) ||
is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value &&
std::is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type>::type;
#else
template <class T> using is_integral = typename std::is_integral<T>;
template <class T>
using is_signed_int =
typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<is_integral<T>::value &&
std::is_unsigned<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type;
#endif
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
} // namespace internal
} // namespace atcoder
namespace atcoder {
namespace internal {
struct modint_base {};
struct static_modint_base : modint_base {};
template <class T> using is_modint = std::is_base_of<modint_base, T>;
template <class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;
} // namespace internal
template <int m, std::enable_if_t<(1 <= m)>* = nullptr>
struct static_modint : internal::static_modint_base {
using mint = static_modint;
public:
static constexpr int mod() { return m; }
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
static_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
static_modint(T v) {
long long x = (long long)(v % (long long)(umod()));
if (x < 0) x += umod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
static_modint(T v) {
_v = (unsigned int)(v % umod());
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v -= rhs._v;
if (_v >= umod()) _v += umod();
return *this;
}
mint& operator*=(const mint& rhs) {
unsigned long long z = _v;
z *= rhs._v;
_v = (unsigned int)(z % umod());
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
if (prime) {
assert(_v);
return pow(umod() - 2);
} else {
auto eg = internal::inv_gcd(_v, m);
assert(eg.first == 1);
return eg.second;
}
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static constexpr unsigned int umod() { return m; }
static constexpr bool prime = internal::is_prime<m>;
};
template <int id> struct dynamic_modint : internal::modint_base {
using mint = dynamic_modint;
public:
static int mod() { return (int)(bt.umod()); }
static void set_mod(int m) {
assert(1 <= m);
bt = internal::barrett(m);
}
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
dynamic_modint() : _v(0) {}
template <class T, internal::is_signed_int_t<T>* = nullptr>
dynamic_modint(T v) {
long long x = (long long)(v % (long long)(mod()));
if (x < 0) x += mod();
_v = (unsigned int)(x);
}
template <class T, internal::is_unsigned_int_t<T>* = nullptr>
dynamic_modint(T v) {
_v = (unsigned int)(v % mod());
}
unsigned int val() const { return _v; }
mint& operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator-=(const mint& rhs) {
_v += mod() - rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint& operator*=(const mint& rhs) {
_v = bt.mul(_v, rhs._v);
return *this;
}
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
auto eg = internal::inv_gcd(_v, mod());
assert(eg.first == 1);
return eg.second;
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static internal::barrett bt;
static unsigned int umod() { return bt.umod(); }
};
template <int id> internal::barrett dynamic_modint<id>::bt(998244353);
using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;
namespace internal {
template <class T>
using is_static_modint = std::is_base_of<internal::static_modint_base, T>;
template <class T>
using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;
template <class> struct is_dynamic_modint : public std::false_type {};
template <int id>
struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};
template <class T>
using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;
} // namespace internal
} // namespace atcoder
using namespace std;
using mint=atcoder::modint;
int N,K,M;
mint comb[201][201];
int trcomb[201][201];
mint ans[1<<17];
mint vec[200];
int nvec[200];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>N>>K>>M;
mint::set_mod(M);
for(int i=0;i<=K;i++)
{
comb[i][0]=comb[i][i]=mint::raw(1);
for(int j=1;j<i;j++)comb[i][j]=comb[i-1][j-1]+comb[i-1][j];
}
for(int i=0;i<=K;i++)for(int j=0;j<=i;j++)trcomb[j][i]=comb[i][j].val();
for(int i=0;i<K;i++)vec[i]=mint::raw(0);
vec[K-1]=mint::raw(1);
for(int n=N;n>=1;n--)
{
if(n<N)
{
const mint inv=mint::raw(n).inv();
for(int i=0;i<K;i++)nvec[i]=(vec[i]*inv).val();
for(int l=0;l<K;l++)
{
__int128 sum=0;
for(int j=l;j<K;j++)sum+=(long long)nvec[j]*trcomb[l][j+1];
vec[l]+=mint::raw(sum%M);
//vec[l]+=nvec[l]*trcomb[l][l+1];
//for(int j=l+1;j<K;j++)vec[l]+=nvec[j]*trcomb[l][j+1];
}
}
ans[n]=mint::raw(0);
for(int i=0;i<K;i++)ans[n]+=vec[i];
}
for(int n=1;n<=N;n++)cout<<ans[n].val()<<(n==N?"\n":" ");
}
这程序好像有点Bug，我给组数据试试？
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 4224kb
input:
3 1 1000000007
output:
3 500000005 1
result:
ok 3 number(s): "3 500000005 1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 4480kb
input:
3 2 998244353
output:
9 499122179 1
result:
ok 3 number(s): "9 499122179 1"
Test #3:
score: 0
Accepted
time: 14ms
memory: 4224kb
input:
100000 2 247500247
output:
99990120 198313538 181648518 9984012 89152757 122606790 144989074 57767836 139713251 181810000 31507456 166275038 47328509 154160535 83327500 58965059 57266005 62816671 182890130 94757428 220071605 169630367 158184542 33329500 49804019 177268667 34308738 1462169 207899265 29486137 36126024 183936623...
result:
ok 100000 numbers
Test #4:
score: 0
Accepted
time: 13ms
memory: 4480kb
input:
93243 2 871928951
output:
846896490 718247765 577098350 41079215 405218914 227159222 310499190 205167702 832611988 705007023 845120518 295904768 823739537 169989571 159639598 28661386 227786795 150269468 541377603 807448870 354698513 504788853 600146531 233880586 541856913 423469197 327480599 74027728 25997100 224019624 8081...
result:
ok 93243 numbers
Test #5:
score: 0
Accepted
time: 10ms
memory: 4352kb
input:
88126 2 815309081
output:
428410147 686328082 479041544 205889612 300318620 20389992 685009094 57186663 226928147 600734124 661202285 507214889 694578908 19604338 105478579 39114733 253249882 660469674 547220370 545575449 181854078 101589195 813903761 115567927 415241080 361254177 318194972 5068568 567012687 53519150 9126832...
result:
ok 88126 numbers
Test #6:
score: 0
Accepted
time: 35ms
memory: 4352kb
input:
100000 20 274295591
output:
133515401 13118380 89106302 78342553 165195888 227060294 52478179 267144515 24472291 43437006 273021769 119052128 11647686 3290431 49050407 171571350 95631399 248844031 35296684 218106957 49127626 169039090 188638802 45352042 93637916 83703846 202348655 242427621 107803831 54794031 252526350 2327816...
result:
ok 100000 numbers
Test #7:
score: 0
Accepted
time: 28ms
memory: 4352kb
input:
88126 19 175327979
output:
158950473 18402437 106235197 22191987 138340285 126056816 124203721 122089700 166866855 86286201 17884807 69131094 27656384 168725914 40019793 69711817 118470230 23394707 18716275 675243 38271008 126222244 118760155 134953966 91892978 24853002 154149875 85732327 78093023 108592897 24813091 61898445 ...
result:
ok 88126 numbers
Test #8:
score: 0
Accepted
time: 28ms
memory: 4480kb
input:
93243 17 521107271
output:
401623247 79539477 350407101 118842666 307611331 145882711 44804642 132585714 324150453 377577997 167442211 191408337 502330545 487993743 77033044 491860232 66453035 19882036 119057636 122698010 12896407 108213680 179249435 16768652 311367825 284266634 330830578 221032368 37875566 13079459 245051661...
result:
ok 93243 numbers
Test #9:
score: 0
Accepted
time: 1630ms
memory: 4608kb
input:
100000 200 180127469
output:
167062212 92524657 166915946 29251783 29827571 4319369 81324107 236099 50093774 52375863 27752593 46678455 147927291 111428702 58058274 28516187 143468295 63746622 86677605 156508086 60090503 123421346 127381103 178968198 34588724 92087953 150913038 4291383 177405489 92727242 169922068 130905337 113...
result:
ok 100000 numbers
Test #10:
score: 0
Accepted
time: 1605ms
memory: 4480kb
input:
99281 199 831673061
output:
739037710 600820702 34103819 114260931 461829617 268804979 631802906 227389899 395384357 402330121 792047383 152088457 559215019 494507217 703460390 222964336 535953767 376723634 324580553 611512391 799481475 696985790 631050926 699196221 84548661 585817140 48372570 633938057 440672424 553087056 256...
result:
ok 99281 numbers
Test #11:
score: 0
Accepted
time: 1470ms
memory: 4480kb
input:
99123 190 184986859
output:
150676314 8306448 32778644 62178449 104286694 62297492 85618916 88596335 17408717 176983517 136446622 102276004 95765785 130390965 69193316 145748571 66260225 105139243 68618676 118327626 97749079 97937844 11088207 119734069 32544048 87920498 93841606 166650044 118169960 17744733 139825728 115301315...
result:
ok 99123 numbers
Test #12:
score: 0
Accepted
time: 13ms
memory: 4224kb
input:
100000 1 998244353
output:
100000 50000 332781451 25000 20000 665512902 285226958 12500 443675268 10000 726004984 332756451 844675991 142613479 665502902 6250 645928699 221837634 315240322 5000 760571888 363002492 130210133 665500402 4000 921460172 147891756 570428916 860558925 332751451 225413241 3125 574749779 822086526 855...
result:
ok 100000 numbers
Test #13:
score: 0
Accepted
time: 13ms
memory: 4352kb
input:
100000 2 998244353
output:
17556470 5835490 668405647 1740647 1157098 48359563 499738479 499600134 554961451 181810000 91007918 665714267 11156053 161014 83327500 14803641 587312080 198579032 262783548 570504423 756317395 457758306 455779873 33329500 798645810 409582602 945470198 791750956 344259332 279113704 535381158 351684...
result:
ok 100000 numbers
Test #14:
score: 0
Accepted
time: 14ms
memory: 4352kb
input:
100000 3 998244353
output:
733427426 178967739 202934029 433340642 532337140 605728396 981959828 737139460 888911107 38920791 183454787 191631176 161311621 621244336 340320388 225674683 431086340 824666829 749376222 796265987 213471341 156036046 277058601 945134678 603493090 462039974 449024634 705230519 414899866 370632747 9...
result:
ok 100000 numbers
Extra Test:
score: 0
Extra Test Passed