結果
| 問題 |
No.8120 Aoki's Present for Takahashi
|
| ユーザー |
👑  Nachia
|
| 提出日時 | 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;
}