結果

問題 No.1184 Hà Nội
コンテスト
ユーザー nonpro3
提出日時 2020-08-22 20:53:54
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 4,667 bytes
コンパイル時間 795 ms
コンパイル使用メモリ 75,444 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-15 12:21:10
合計ジャッジ時間 1,762 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>

using namespace std;

typedef long long ll;

//このnamespace内のMODという値を、問題の要求に応じて変更すること
namespace Mint {

	//このMODという値を、問題の要求に応じて変更すること
	const ll MOD = 998244353;

	template<ll Mod>
	struct Modint {
		ll val = 0;

		//コンストラクタ long long, 空, Modintを受け取れる
		Modint() = default;
		Modint(const Modint&) = default;
		Modint(ll _x) {
			val = _x >= 0 ? _x % Mod : ((_x % Mod) + Mod) % Mod;
		}

		//繰り返し二乗法、逆元　基本的に外部からいじるのやめたほうがよさそう。
		ll modpow(ll a, ll b) const {
			ll ret = 1, kakeru = a;
			while (b > 0) {
				if (b & 1)ret *= kakeru, ret %= Mod;
				kakeru *= kakeru, kakeru %= Mod;
				b >>= 1;
			}
			return ret;
		}
		Modint inv() const {
			return modpow((*this).val, MOD - 2);
		}

		//代入演算子　Modintとlong longの2通りある
		Modint operator= (const Modint& p) {
			val = p.val;
			return (*this);
		}

		//二項演算＋代入演算子　二項演算子、同値演算子はクラス外で定義する
		Modint& operator+= (const Modint& p) {
			val += p.val;
			if (val >= Mod)val -= Mod;
			return (*this);
		}
		Modint& operator-= (const Modint& p) {
			val -= p.val;
			if (val < 0)val += Mod;
			return (*this);
		}
		Modint& operator*= (const Modint& p) {
			val *= p.val;
			val %= Mod;
			return (*this);
		}
		Modint& operator/= (const Modint& p) {
			//なんか,p.inv()を使うとthisのポインターが変換できませんって出る
			//Modint tmp(p.inv());
			Modint tmp(modpow(p.val, MOD - 2));
			(*this) *= tmp;
			return (*this);
		}
	};

	//加算
	const Modint<MOD> operator+ (const Modint<MOD>& l, const Modint<MOD>& r) {
		Modint<MOD> tmp = l;
		tmp += r;
		return tmp;
	}
	const Modint<MOD> operator+ (const Modint<MOD>& l, const ll r) {
		Modint<MOD> tmp = l;
		tmp += Modint<MOD>(r);
		return tmp;
	}
	const Modint<MOD> operator+ (const ll l, const Modint<MOD>& r) {
		Modint<MOD> tmp = l;
		tmp += r;
		return tmp;
	}
	//減算
	const Modint<MOD> operator- (const Modint<MOD>& l, const Modint<MOD>& r) {
		Modint<MOD> tmp = l;
		tmp -= r;
		return tmp;
	}
	const Modint<MOD> operator- (const Modint<MOD>& l, const ll r) {
		Modint<MOD> tmp = l;
		tmp -= Modint<MOD>(r);
		return tmp;
	}
	const Modint<MOD> operator- (const ll l, const Modint<MOD>& r) {
		Modint<MOD> tmp = l;
		tmp -= r;
		return tmp;
	}
	//乗算
	const Modint<MOD> operator* (const Modint<MOD>& l, const Modint<MOD>& r) {
		Modint<MOD> tmp = l;
		tmp *= r;
		return tmp;
	}
	const Modint<MOD> operator* (const Modint<MOD>& l, const ll r) {
		Modint<MOD> tmp = l;
		tmp *= Modint<MOD>(r);
		return tmp;
	}
	const Modint<MOD> operator* (const ll l, const Modint<MOD>& r) {
		Modint<MOD> tmp = l;
		tmp *= r;
		return tmp;
	}
	//除算
	const Modint<MOD> operator/ (const Modint<MOD>& l, const Modint<MOD>& r) {
		Modint<MOD> tmp = l;
		tmp /= r;
		return tmp;
	}
	const Modint<MOD> operator/ (const Modint<MOD>& l, const ll r) {
		Modint<MOD> tmp = l;
		tmp /= Modint<MOD>(r);
		return tmp;
	}
	const Modint<MOD> operator/ (const ll l, const Modint<MOD>& r) {
		Modint<MOD> tmp = l;
		tmp /= r;
		return tmp;
	}
	//同値演算子
	const bool operator== (const Modint<MOD>& l, const Modint<MOD>& r) {
		return l.val == r.val;
	}
	const bool operator== (const Modint<MOD>& l, const ll r) {
		return l.val == r;
	}
	const bool operator== (const ll l, const Modint<MOD>& r) {
		return l == r.val;
	}
	const bool operator!= (const Modint<MOD>& l, const Modint<MOD>& r) {
		return !(l.val == r.val);
	}
	const bool operator!= (const Modint<MOD>& l, const ll r) {
		return !(l.val == r);
	}
	const bool operator!= (const ll l, const Modint<MOD>& r) {
		return !(l == r.val);
	}
	//istream ostream での入出力サポート
	std::ostream& operator<<(std::ostream& stream, const Modint<MOD>& p) {
		stream << p.val;
		return stream;
	}
	std::istream& operator>>(std::istream& stream, Modint<MOD>& p) {
		stream >> p.val;
		return stream;
	}
	//使う用の繰り返し二乗法 bはlong long に注意
	Modint<MOD> modpow(const Modint<MOD> a, ll b) {
		ll ret = 1, kakeru = a.val;
		while (b > 0) {
			if (b & 1)ret *= kakeru, ret %= MOD;
			kakeru *= kakeru, kakeru %= MOD;
			b >>= 1;
		}
		Modint<MOD> tmpret(ret);
		return tmpret;
	}
}

using namespace Mint;
using mint = Mint::Modint<MOD>;


ll n, k;

int main() {
	cin >> n >> k;
	if (n == k) {
		cout << 1 << endl;
		return 0;
	}
	ll s = n / k;
	if (n % k != 0)s++;
	cout << modpow(2, s) - 1 << endl;

	return 0;
}
0