結果
問題 |
No.8120 Aoki's Present for Takahashi
|
ユーザー |
👑 ![]() |
提出日時 | 2025-04-01 22:34:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 173 ms / 2,000 ms |
コード長 | 6,691 bytes |
コンパイル時間 | 1,346 ms |
コンパイル使用メモリ | 94,100 KB |
実行使用メモリ | 12,164 KB |
最終ジャッジ日時 | 2025-04-01 23:16:09 |
合計ジャッジ時間 | 5,457 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 20 |
ソースコード
#ifdef NACHIA #define _GLIBCXX_DEBUG #else #define NDEBUG #endif #include <iostream> #include <string> #include <vector> #include <algorithm> using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(i64 i=0; i<i64(n); i++) const i64 INF = 1001001001001001001; template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; } template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; } using namespace std; #include <atcoder/modint> #include <cassert> #include <utility> namespace nachia{ // ax + by = gcd(a,b) // return ( x, - ) std::pair<long long, long long> ExtGcd(long long a, long long b){ long long x = 1, y = 0; while(b){ long long u = a / b; std::swap(a-=b*u, b); std::swap(x-=y*u, y); } return std::make_pair(x, a); } } // namespace nachia namespace nachia{ class DynamicModSupplier{ using u64 = unsigned long long; using Int = unsigned int; private: u64 imod; Int mod; // atcoder library u64 reduce2(u64 z) const noexcept { // atcoder library #ifdef _MSC_VER u64 x; _umul128(z, im, &x); #else using u128 = unsigned __int128; u64 x = (u64)(((u128)(z)*imod) >> 64); #endif return z - x * mod; } public: DynamicModSupplier(unsigned int MOD = 998244353) : mod(MOD) { assert(2 <= MOD); assert(MOD < (1u << 31)); imod = (u64)(-1) / mod + 1; } Int reduce(u64 z) const noexcept { Int v = reduce2(z); if(mod <= v) v += mod; return v; } Int add(Int a, Int b) const { a += b; if(a >= mod){ a -= mod; } return a; } Int sub(Int a, Int b) const { a -= b; if(a >= mod){ a += mod; } return a; } Int mul(Int a, Int b) const { return reduce((u64)a * b); } Int muladd(Int a, Int b, Int c) const { return reduce((u64)a * b + c); } Int inv(Int a) const { Int v = ExtGcd(a, mod).first; return (v < mod) ? v : (v + mod); } Int pow(Int a, u64 i) const { Int r = a, ans = 1; while(i){ if(i & 1) ans = mul(ans, r); i /= 2; r = mul(r, r); } return ans; } Int getMod() const { return mod; } }; } // namespace nachia namespace nachia{ template<class FinishType> struct GarnerMod{ using Int = unsigned int; using IntLong = unsigned long long; std::vector<Int> mods; std::vector<DynamicModSupplier> dynmods; std::vector<std::vector<Int>> table_coeff; std::vector<Int> table_coeffinv; void precalc(std::vector<Int> new_mods){ mods = std::move(new_mods); dynmods.resize(mods.size()); for(size_t i=0; i<mods.size(); i++) dynmods[i] = DynamicModSupplier(mods[i]); int nmods = mods.size(); table_coeff.assign(nmods+1, std::vector<Int>(nmods, 1)); for(int j=0; j<nmods; j++){ for(int k=0; k<nmods; k++) table_coeff[j+1][k] = table_coeff[j][k]; for(int k=j+1; k<nmods; k++) table_coeff[j+1][k] = dynmods[k].mul(table_coeff[j+1][k], mods[j] % mods[k]); } table_coeffinv.resize(nmods); for(int i=0; i<nmods; i++) table_coeffinv[i] = dynmods[i].inv(table_coeff[i][i]); } FinishType calc(const std::vector<Int>& x) const { int nmods = mods.size(); std::vector<Int> table_const(nmods); FinishType res = 0; FinishType res_coeff = 1; for(int j=0; j<nmods; j++){ Int t = dynmods[j].mul(dynmods[j].sub(x[j], table_const[j]), table_coeffinv[j]); for(int k=j+1; k<nmods; k++){ table_const[k] = dynmods[k].muladd(t, table_coeff[j][k], table_const[k]); } res += res_coeff * FinishType(t); res_coeff *= mods[j]; } return res; } std::vector<FinishType> calc(std::vector<std::vector<Int>> x) const { int n = x[0].size(), m = x.size(); std::vector<FinishType> res(n); std::vector<Int> buf(m); for(int i=0; i<n; i++){ for(int j=0; j<m; j++) buf[j] = x[j][i]; res[i] = calc(buf); } return res; } }; } // namespace nachia namespace nachia { struct CombinationAnyMod { using Int = unsigned int; using Int2 = long long; CombinationAnyMod() {} CombinationAnyMod(Int m){ std::vector<Int> mods; for(Int p=2; p*p<=m; p++) if(m%p == 0){ Int pe = 1; int e = 0; do{ e += 1; pe *= p; m /= p; } while(m%p == 0); mpf.emplace_back(p, pe, e); mods.push_back(pe); } if(m != 1){ mpf.emplace_back(m, m, 1); mods.push_back(m); } mg.precalc(mods); } Int comb(Int2 n, Int2 r) const { std::vector<Int> rems; for(auto& f : mpf) rems.push_back(f.comb(n, r)); return mg.calc(rems); } Int operator()(Int2 n, Int2 r) const { return comb(n,r); } private: struct CombinationModPrimePower{ DynamicModSupplier dyn; std::vector<Int> F; Int p; int e; CombinationModPrimePower(Int xp, Int xm, int xe) : dyn(xm), F(xm+1), p(xp), e(xe) { F[0] = 1; for(Int s=0; s<xm; s+=p){ for(Int i=1; i<p; i++) F[s+i] = dyn.mul(F[s+i-1], s+i); F[s+p] = F[s+p-1]; } } std::pair<Int2, Int> fact(Int2 n) const { Int2 ze = 0; Int2 qe = 0; Int f = 1; int k = 0; while(n){ Int x = n % dyn.getMod(); f = dyn.mul(f, F[x]); n /= p; ze += n; if(++k >= e) qe += n; } if(qe % 2 == 1 && !(p == 2 && e >= 3)) f = dyn.getMod() - f; return { ze, f }; } Int comb(Int2 n, Int2 r) const { if(r < 0 || n < r) return 0; auto [ne, nf] = fact(n); auto [re, rf] = fact(r); auto [se, sf] = fact(n-r); Int2 ze = ne - re - se; if(e <= ze) return 0; Int f = dyn.mul(nf, dyn.inv(dyn.mul(rf, sf))); for(int i=0; i<int(ze); i++) f = dyn.mul(f, p); return f; } }; std::vector<CombinationModPrimePower> mpf; GarnerMod<Int> mg; }; } // namespace nachia auto comb = nachia::CombinationAnyMod(998243353); void testcase(){ i64 T, Tau; cin >> T >> Tau; rep(t,Tau){ i64 N, M; cin >> M >> N; if(t != T-1) cout << comb(N,M) << "\n"; else cout << "-1\n"; } } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); testcase(); return 0; }