結果

問題 No.1206 OR, OR, OR......
ユーザー piddy
提出日時 2020-09-04 15:21:09
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 5,388 bytes
コンパイル時間 9,563 ms
コンパイル使用メモリ 244,108 KB
最終ジャッジ日時 2025-01-14 04:27:32
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:51:19: error: expected unqualified-id before 'long'
   51 |         modint<M>(long long right) : val(right) {sub(val);}
      |                   ^~~~
main.cpp:51:19: error: expected ')' before 'long'
   51 |         modint<M>(long long right) : val(right) {sub(val);}
      |                  ~^~~~
      |                   )
main.cpp:52:19: error: expected unqualified-id before ')' token
   52 |         modint<M>() {val = 0;}
      |                   ^
main.cpp: In function 'int main()':
main.cpp:179:33: error: conversion from 'int' to non-scalar type 'modint<998244353>' requested
  179 |                 modint<P> ans = 0;
      |                                 ^
main.cpp: In instantiation of 'modint<P> modpow(long long int, long long int) [with long long int M = 998244353]':
main.cpp:180:21:   required from here
main.cpp:150:28: error: could not convert '1' from 'int' to 'modint<998244353>'
  150 |         if (n == 0) return 1;
      |                            ^
      |                            |
      |                            int
main.cpp:151:28: error: could not convert '0' from 'int' to 'modint<998244353>'
  151 |         if (a == 0) return 0;
      |                            ^
      |                            |
      |                            int
main.cpp:152:28: error: could not convert '1' from 'int' to 'modint<998244353>'
  152 |         if (a == 1) return 1;
      |                            ^
      |                            |
      |                            int
main.cpp:159:24: error: no match for 'operator=' (operand types are 'modint<998244353>' and 'long long int')
  159 |         if (b < M) ret = b;
      |                    ~~~~^~~
main.cpp:48:8: note: candidate: 'constexpr modint<998244353>& modint<998244353>::operator=(const modint<998244353>&)'
   48 | struct modint {
      |        ^~~~~~
main.cpp:48:8: note:   no known conversion for argument 1 from 'long long int' to 'const modint<998244353>&'
main.cpp:48:8: no

ソースコード

diff # 

#include <bits/stdc++.h>
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define FSP(x) fixed << setprecision(x)
using namespace std;
using ll = long long;
constexpr ll INF = LLONG_MAX;
//constexpr ll P = 1e9 + 7;
constexpr ll P = 998244353;
constexpr long double PI = acosl(-1);
void Yes() {cout << "Yes\n";}
void No() {cout << "No\n";}
void YES() {cout << "YES\n";}
void NO() {cout << "NO\n";}

#include <iostream>
#include <vector>

/*	NOTICE : followings requires template argument to be prime
		- use of modinv
		- division by modint
		- use of factorial_inv
*/

/*	verified : 2020/07/30
		AtCoder, Knapsack for All Subsets
		https://atcoder.jp/contests/abc169/tasks/abc169_f
		AtCoder, Bouquet
		https://atcoder.jp/contests/abc156/tasks/abc156_d
*/

template<long long P>
long long modinv(long long n) {
	long long a = P, u = 1, v = 0;
	while (a) {
		long long t = n / a;
		n -= t * a;
		std::swap(n, a);
		u -= t * v;
		std::swap(u, v);
	}
	u %= P;
	if (u < 0) u += P;
	return u;
}

template<long long M>
struct modint {
	long long val;

	modint<M>(long long right) : val(right) {sub(val);}
	modint<M>() {val = 0;}

	void sub(long long &n) {
		if (n < 0) {
			long long m = (-n) % M;
			n = M - m;
		}
		else n %= M;
	}

	modint<M> operator+ (modint<M> right) {return (this -> val) + right.val;}
	modint<M> operator+ (long long right) {sub(right); return (this -> val) + right;}
	modint<M> operator- (modint<M> right) {return (this -> val) - right.val;}
	modint<M> operator- (long long right) {sub(right); return (this -> val) - right;}
	modint<M> operator* (modint<M> right) {return (this -> val) * right.val;}
	modint<M> operator* (long long right) {sub(right); return (this -> val) * right;}

	bool operator== (modint<M> right) {return ((this -> val) == right.val);}
	bool operator== (long long right) {sub(right); return ((this -> val) == right);}
	bool operator!= (modint<M> right) {return ((this -> val) != right.val);}
	bool operator!= (long long right) {sub(right); return ((this -> val) != right);}
	bool operator<= (modint<M> right) {return ((this -> val) <= right.val);}
	bool operator<= (long long right) {sub(right); return ((this -> val) <= right);}
	bool operator>= (modint<M> right) {return ((this -> val) >= right.val);}
	bool operator>= (long long right) {sub(right); return ((this -> val) >= right);}
	bool operator< (modint<M> right) {return ((this -> val) < right.val);}
	bool operator< (long long right) {sub(right); return ((this -> val) < right);}
	bool operator> (modint<M> right) {return ((this -> val) > right.val);}
	bool operator> (long long right) {sub(right); return ((this -> val) > right);}

	void operator+= (modint<M> right) {*this = *this + right;}
	void operator+= (long long right) {*this = *this + right;}
	void operator-= (modint<M> right) {*this = *this - right;}
	void operator-= (long long right) {*this = *this - right;}
	void operator*= (modint<M> right) {*this = *this * right;}
	void operator*= (long long right) {*this = *this * right;}

	modint<M>& operator++ () {*this += 1; return *this;}
	modint<M> operator++ (int) {*this += 1; return *this - 1;}
	modint<M>& operator-- () {*this -= 1; return *this;}
	modint<M> operator-- (int) {*this -= 1; return *this + 1;}

	modint<M> operator/ (modint<M> right) {return *this * modinv<M>(right.val);}
	modint<M> operator/ (long long right) {sub(right); return *this * modinv<M>(right);}

	void operator/= (modint<M> right) {*this = *this / right;}
	void operator/= (long long right) {*this = *this / right;}
};

std::vector<long long> factorial;
std::vector<long long> factorial_inv;

template<long long P>
void make_table(long long n) {
	factorial.resize(n + 1, 1); factorial_inv.resize(n + 1, 1);
	for (long long i = 2; i <= n; i++) {
		factorial[i] = factorial[i - 1] * i % P;
	}
	factorial_inv[n] = modinv<P>(factorial[n]);
	for (long long i = n - 1; i >= 0; i--) {
		factorial_inv[i] = factorial_inv[i + 1] * (i + 1) % P;
	}
}

template<long long P>
modint<P> permutation(long long n, long long r) {
	if (n <= factorial.size()) {
		modint<P> a = factorial[n], b = factorial_inv[n - r];
		return a * b;
	}
	else {
		std::cerr << "attention : factorial table is not constructed" << '\n';
		modint<P> ret = 1;
		for (long long i = 0; i < r; i++) ret *= n - i;
		return ret;
	}
}

template<long long P>
modint<P> combination(long long n, long long r) {
	r = std::min(r, n - r);
	if (n <= factorial.size()) {
		return permutation<P>(n, r) * factorial_inv[r];
	}
	else {
		std::cerr << "attention : factorial table is not constructed" << '\n';
		modint<P> ret = 1;
		for (long long i = 0; i < r; i++) {
			ret *= n - i;
			ret /= i + 1;
		}
		return ret;
	}
}

template<long long M>
modint<M> modpow(long long a, long long n) {
	a %= M;
	if (n == 0) return 1;
	if (a == 0) return 0;
	if (a == 1) return 1;
	long long b = 1, cnt = 0;
	while (b < M && cnt < n) {
		b *= a;
		cnt++;
	}
	modint<M> ret;
	if (b < M) ret = b;
	else {
		b %= M;
		ret = modpow<M>(b, n / cnt) * modpow<M>(a, n % cnt);
	}
	return ret;
}

template<long long M>
std::ostream &operator<< (std::ostream &out, modint<M> tgt) {out << tgt.val; return out;}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	ll t;
	cin >> t;
	while (t--) {
		ll n, k;
		cin >> n >> k;
		modint<P> ans = 0;
		cout << (modpow<P>(2, k) - 1) * modpow<P>(modpow<P>(2, k).val, n - 1) * n << '\n';
	}
}
0