#188518 (C++17) No.510 二次漸化式

提出ソース

結果

問題	No.510 二次漸化式
ユーザー	WA_TLE
提出日時	2017-07-14 15:18:26
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	70 ms / 3,000 ms
コード長	7,403 bytes
コンパイル時間	1,796 ms
コンパイル使用メモリ	130,396 KB
実行使用メモリ	11,776 KB
最終ジャッジ日時	2024-04-16 19:48:08
合計ジャッジ時間	4,863 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	36 ms 5,376 KB
testcase_03	AC	37 ms 5,376 KB
testcase_04	AC	37 ms 5,376 KB
testcase_05	AC	36 ms 5,376 KB
testcase_06	AC	45 ms 5,376 KB
testcase_07	AC	46 ms 5,376 KB
testcase_08	AC	45 ms 5,376 KB
testcase_09	AC	46 ms 5,376 KB
testcase_10	AC	28 ms 5,376 KB
testcase_11	AC	27 ms 5,376 KB
testcase_12	AC	27 ms 5,376 KB
testcase_13	AC	27 ms 5,376 KB
testcase_14	AC	26 ms 5,376 KB
testcase_15	AC	27 ms 5,376 KB
testcase_16	AC	36 ms 8,704 KB
testcase_17	AC	36 ms 8,576 KB
testcase_18	AC	36 ms 8,576 KB
testcase_19	AC	35 ms 8,576 KB
testcase_20	AC	36 ms 8,576 KB
testcase_21	AC	36 ms 8,704 KB
testcase_22	AC	35 ms 8,576 KB
testcase_23	AC	67 ms 11,392 KB
testcase_24	AC	69 ms 11,264 KB
testcase_25	AC	70 ms 11,008 KB
testcase_26	AC	67 ms 11,264 KB
testcase_27	AC	68 ms 11,136 KB
testcase_28	AC	68 ms 11,136 KB
testcase_29	AC	67 ms 11,008 KB
testcase_30	AC	67 ms 11,136 KB
testcase_31	AC	61 ms 11,776 KB
testcase_32	AC	62 ms 11,776 KB
testcase_33	AC	62 ms 11,776 KB
testcase_34	AC	68 ms 10,368 KB
testcase_35	AC	49 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include<string>
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include <iomanip>
#include<set>
#include<cmath>
#include<tuple>
#include<chrono>
#include<functional>
#include<random>
#include<unordered_set>
using namespace std;
typedef long long int llint;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
const llint mod=1000000007;
const llint big=1e17-10;
const long double pai=3.141592653589793238462643383279;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
#include <algorithm>
#include <utility>
#include <type_traits>
#include <cstdint>
//永夜作
template<typename Arithmetic, typename Integral>
std::enable_if_t< std::is_unsigned<Integral>::value, Arithmetic>
ipow(Arithmetic bace, Integral n)
{
	//繰り返し二条法
	auto res = (Arithmetic)(1);
	while (n > 0) {
		if (n & 1) res *= bace;
		bace *= bace;
		n >>= 1;
	}
	return res;
}
template <uint64_t MOD> class mint_base;
//mint_base_base型用の累乗関数
template <uint64_t MOD> constexpr mint_base<MOD> m_pow(mint_base<MOD> x, uint64_t n)noexcept;
//mod計算を自動で行う整数テンプレートクラス
template <uint64_t MOD_ = 1000000007>
class mint_base
{
public:
	//operator llint() const{return a;}
	static constexpr auto MOD = MOD_;
	static_assert(!(MOD <= 2), "MOD cannot be below 2.");
	static_assert(MOD <= (0xFFFFFFFFFFFFFFFF / 2), "MOD is too big");//加算してオーバーフローしない
	static_assert(MOD <= 0xFFFFFFFF, "MOD is too big");//乗算してオーバーフローしない
	constexpr mint_base<MOD> operator+(const mint_base<MOD> &other)const noexcept
	{
		auto v = *this;
		return v += other;
	}
	constexpr mint_base<MOD> operator-(const mint_base<MOD> &other)const noexcept
	{
		auto v = *this;
		return v -= other;
	}
	constexpr mint_base<MOD> operator*(const mint_base<MOD> &other)const noexcept
	{
		auto v = *this;
		return v *= other;
	}
	constexpr auto operator/(const mint_base<MOD> &other)const noexcept
	{
		auto v = *this;
		return v /= other;
	}
	constexpr mint_base<MOD>& operator+=(const mint_base<MOD> &other) noexcept
	{
		a += other.a;
		if (MOD <= a) { a -= MOD; };
		return *this;
	}
	constexpr mint_base<MOD>& operator-=(const mint_base<MOD> &other) noexcept
	{
		if (a >= other.a) {
			a -= other.a;
		}
		else {
			a = (a + MOD) - other.a;
		}
		return *this;
	}
	constexpr mint_base<MOD>& operator*=(const mint_base<MOD> &other) noexcept
	{
#if 1
		a *= other.a;
		a %= MOD;
#else
		//MOD <= (MAXUINT64 / 2)条件下
		uint64_t b = other.a, v = 0;
		while (b > 0) {
			if (b & 1) {
				v += a;
				if (v >= MOD)v -= MOD;
			}
			a += a;
			if (MOD <= a)a -= MOD;
			b >>= 1;
		}
		a = v;
#endif
		return *this;
	}
	constexpr mint_base<MOD>& operator/=(const mint_base<MOD> &other) noexcept
	{
		return *this *= ~other;
	}
	constexpr mint_base<MOD> operator+()const noexcept { return *this; }
	constexpr mint_base<MOD> operator-()const noexcept
	{
		return{ MOD - a, mod_value_tag{} };
	}
	constexpr mint_base<MOD>& operator++() noexcept
	{
		if (MOD <= ++a) { a = 0; };
		return *this;
	}
	constexpr mint_base<MOD>& operator--() noexcept
	{
		if (a <= 0) { a = MOD; };
		--a;
		return *this;
	}
	constexpr mint_base<MOD> operator++(int) noexcept
	{
		auto tmp = *this;
		++*this;
		return tmp;
	}
	constexpr mint_base<MOD> operator--(int) noexcept
	{
		auto tmp = *this;
		--*this;
		return tmp;
	}
	constexpr mint_base<MOD> operator~()const noexcept
	{
		return ipow(*this, e_phi - 1);
	}
	constexpr mint_base<MOD>& operator=(const mint_base<MOD> &other) noexcept
	{
		a = other.a;
		return *this;
	}
	constexpr explicit operator uint64_t()const noexcept
	{
		return a;
	}
	constexpr explicit operator unsigned()const noexcept
	{
		return (unsigned)a;
	}
	static constexpr uint64_t getmod() noexcept
	{
		return MOD;
	}
	constexpr mint_base(uint64_t a_) noexcept :a(a_ % MOD) {}
	constexpr mint_base()noexcept : a(0) {}
	struct mod_value_tag {};
	constexpr mint_base(uint64_t a_, mod_value_tag) :a(a_) {}
private:
	static constexpr uint64_t get_e_phi()noexcept {
		//オイラー値の導出
		uint64_t temp = MOD;
		uint64_t m_ = MOD;
		for (uint64_t i = 2; i * i <= m_; ++i)
		{
			if (m_ % i == 0)
			{
				temp = temp / i * (i - 1);
				for (; m_ % i == 0; m_ /= i);
			}
		}
		if (m_ != 1)temp = temp / m_ * (m_ - 1);
		return temp;
	}
	static constexpr uint64_t e_phi = get_e_phi();//オイラー値
	uint64_t a;
};
//mint_base型のstreamへの出力
template<uint64_t MOD> std::ostream& operator<<(std::ostream& os, mint_base<MOD> i)
{
	os << (uint64_t)i;
	return os;
}
//mint_base型のstreamからの入力
template<uint64_t MOD> std::istream& operator >> (std::istream& is, mint_base<MOD>& i)
{
	uint64_t tmp;
	is >> tmp;
	i = tmp;
	return is;
}
typedef mint_base<1000000007> mint;
namespace mint_literal {
	constexpr mint operator""_mi(unsigned long long x)noexcept {
		return mint(x);
	}
}
class segobj{
	public:mint_base<mod> p,q,r,s,t;
	segobj(void){p=0;q=0;r=0;s=0;t=1;}
	segobj(mint_base<mod> a,mint_base<mod> b,mint_base<mod> c,mint_base<mod> d,mint_base<mod> e){p=a;q=b;r=c;s=d;t=e;}
};//セグ木に乗せるもの
segobj objtani=segobj(0,0,0,0,1);//単位元or初期値 実はconstです(頭がない)
segobj ope(segobj lef,segobj rig){
	return segobj(
		lef.p + rig.p*lef.s*lef.s,
		lef.q + rig.q*lef.s + lef.s*lef.t*rig.p*(mint_base<mod>)2,
		lef.r + rig.r + lef.t*rig.q + lef.t*lef.t*rig.p,
		lef.s*rig.s,
		lef.t*rig.s + rig.t
	);
}//オブジェクトの演算
class seg_tree_mono{
public:
	//区間加算できない代わりに、早く?、任意のモノイド演算が可能です
	//セグ木に変なものを乗せれる!!
	//区間を作るのを遅延します。区間が10^12あってっもおｋ
	segobj val;
	llint seghi,segmg;
	seg_tree_mono *left;
	seg_tree_mono *right;
	seg_tree_mono(llint hi,llint mg){
		seghi=hi;segmg=mg;val=objtani;
		left=nullptr;right=nullptr;
	}
	~seg_tree_mono(){delete left;delete right;}
	void make_ko(void){
		if(this->left==nullptr&&segmg-seghi>1){
			this->left=new seg_tree_mono(seghi,(seghi+segmg)/2);
			this->right=new seg_tree_mono((seghi+segmg)/2,segmg);
		}
	}
	void seg_chan(llint pot,segobj kou){
		//更新クエリ
		if(this->seghi+1==this->segmg){this->val=kou;return;}
		make_ko();
		if(pot<left->segmg){left->seg_chan(pot,kou);}
		else{right->seg_chan(pot,kou);}
		this->val=ope(left->val,right->val);
		return;
	}
	segobj ask_mono(llint hi,llint mg){
		//区間演算クエリー
		if(hi<=seghi&&segmg<=mg){return this->val;}
			if(mg<=seghi||segmg<=hi){return segobj(0,0,0,1,0);}
		make_ko();
		segobj leret,riret;
		leret=left->ask_mono(hi,mg);
		riret=right->ask_mono(hi,mg);
		return ope(leret,riret);
	}

};

int main(void){
	llint n,m;cin>>n>>m;
	seg_tree_mono siki(0,n+1);
	for(int i=0;i<m;i++){
		char que;cin>>que;
		if(que=='x'){
			llint j,v;cin>>j>>v;
			auto it=siki.ask_mono(j,j+1);
			it.p=v;
			siki.seg_chan(j,it);
		}else if(que=='y'){
			llint j,v;cin>>j>>v;
			auto it=siki.ask_mono(j,j+1);
			it.s=v;
			siki.seg_chan(j,it);
		}else if(que=='a'){
			int j;cin>>j;
			auto it=siki.ask_mono(0,j);
			cout<<(it.p+it.q+it.r+(mint_base<mod>)1)<<endl;
		}
	}
	return 0;
}

yukicoder

結果

テストケース

ソースコード