結果
| 問題 | No.3495 ２変数半二項展開 |
| コンテスト | |
| ユーザー |
👑  Nachia
|
| 提出日時 | 2026-04-03 22:14:42 |
| 言語 | C++17 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 45 ms / 2,000 ms |
| コード長 | 6,489 bytes |
| 記録 | |
| コンパイル時間 | 713 ms |
| コンパイル使用メモリ | 105,732 KB |
| 実行使用メモリ | 6,400 KB |
| 最終ジャッジ日時 | 2026-04-03 22:14:55 |
| 合計ジャッジ時間 | 2,387 ms |
|
ジャッジサーバーID （参考情報） |
judge4_0 / judge3_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 20 |
ソースコード
#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
// disable assert
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;
#define REP(i,n) for(ll i=0; i<ll(n); i++)
template <class T> using V = vector<T>;
template <class A, class B> void chmax(A& l, const B& r){ if(l < r) l = r; }
template <class A, class B> void chmin(A& l, const B& r){ if(r < l) l = r; }
#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<unsigned int IDENTIFER, class IDENTIFER2 = void>
class DynamicModint{
using Int = unsigned int;
using MyType = DynamicModint;
private:
static DynamicModSupplier _c;
Int v;
template< class Elem >
static Elem SafeMod(Elem x, Int mod){
if(x < 0){
if(0 <= x+mod) return x + mod;
return mod - ((-(x+mod)-1) % mod + 1);
}
return x % mod;
}
public:
DynamicModint() : v(0) {}
DynamicModint(const MyType& r) : v(r.v) {}
MyType& operator=(const MyType&) = default;
DynamicModint(long long x){ v = SafeMod(x, _c.getMod()); }
static MyType raw(Int _v){ MyType res; res.v = _v; return res; }
static void setMod(DynamicModSupplier sup){ _c = std::move(sup); }
MyType operator+=(MyType r){ return v = _c.add(v, r.v); }
MyType operator+(MyType r) const { return raw(_c.add(v, r.v)); }
MyType operator-=(MyType r){ return v = _c.sub(v, r.v); }
MyType operator-(MyType r) const { return raw(_c.sub(v, r.v)); }
MyType operator-() const { return raw(v ? _c.getMod()-v : 0); }
MyType operator*=(MyType r){ return v = _c.mul(v, r.v); }
MyType operator*(MyType r) const { return raw(_c.mul(v, r.v)); }
MyType operator/=(MyType r){ return v = _c.mul(v, _c.inv(r.v)); }
MyType operator/(MyType r) const { return raw(_c.mul(v, _c.inv(r.v))); }
MyType inv() const { return raw(_c.inv(v)); }
MyType pow(unsigned long long r) const { return raw(_c.pow(v, r)); }
MyType mulAdd(MyType mul, MyType add) const { return raw(_c.muladd(v, mul.v, add.v)); }
Int val() const { return v; }
Int operator*() const { return v; }
static Int mod(){ return _c.getMod(); }
};
template<unsigned int IDENTIFER, class IDENTIFER2>
DynamicModSupplier DynamicModint<IDENTIFER, IDENTIFER2>::_c;
} // namespace nachia
using Mint = nachia::DynamicModint<998244353>;
namespace nachia{
template<class Elem>
struct MatrixOnRing{
private:
int h;
int w;
std::vector<Elem> elems;
public:
MatrixOnRing(int new_h=0, int new_w=0){ h = new_h; w = new_w; elems.resize(h * w); }
MatrixOnRing(MatrixOnRing const&) = default;
int numRow() const { return h; }
int numColumn() const { return w; }
int height() const { return numRow(); }
int width() const { return numColumn(); }
typename std::vector<Elem>::iterator operator[](int y){ return elems.begin() + (y*w); }
typename std::vector<Elem>::const_iterator operator[](int y) const { return elems.begin() + (y*w); }
static MatrixOnRing Identity(int idx, Elem One){ auto res = MatrixOnRing(idx, idx); for(int i=0; i<idx; i++) res[i][i] = One; return res; }
void swapColumns(int x1, int x2){
assert(0 <= x1 && x1 < numColumn());
assert(0 <= x2 && x2 < numColumn());
if(x1 == x2) return;
for(int y=0; y<numRow(); y++) std::swap((*this)[y][x1], (*this)[y][x2]);
}
void swapRows(int y1, int y2){
assert(0 <= y1 && y1 < numRow());
assert(0 <= y2 && y2 < numRow());
if(y1 == y2) return;
for(int x=0; x<numColumn(); x++) std::swap((*this)[y1][x], (*this)[y2][x]);
}
MatrixOnRing operator*(const MatrixOnRing& r) const {
assert(width() == r.height());
auto res = MatrixOnRing(h, r.w);
for(int i=0; i<h; i++) for(int j=0; j<w; j++) for(int k=0; k<r.w; k++) res[i][k] = res[i][k] + (*this)[i][j] * r[j][k];
return res;
}
MatrixOnRing pow(unsigned long long i){
if(i == 0) return Identity(h, Elem(1));
if(i == 1) return *this;
auto a = *this;
auto res = a; i--;
while(i){
if(i % 2 == 1) res = res * a;
a = a * a;
i /= 2;
}
return res;
}
};
} // namespace nachia
void testcase(){
ll N, M, L, B; cin >> N >> M >> L >> B;
Mint::setMod(B);
using Mat = nachia::MatrixOnRing<Mint>;
Mat A(2, 2), Z(2, 2);
A[0][0] = 1; A[0][1] = 1;
A[1][0] = M; A[1][1] = L;
Z[0][0] = L; Z[0][1] = 1;
Z[1][0] = M; Z[1][1] = 1;
Mat h = (A * Z).pow(N / 2) * A.pow(N % 2);
cout << h[0][0].val() << "\n";
}
int main(){
cin.tie(0)->sync_with_stdio(0);
ll T; cin >> T; REP(t,T)
testcase();
return 0;
}