提出 #73913597

---

ソースコード 拡げる

#include<bits/stdc++.h>
#include<unordered_map>
#include<chrono>
using namespace std;
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define pii pair<int,int>
#define pll pair<long long,long long>
#define fi first
#define se second

#define int long long
#define Int __int128
#define ld long double

template<typename T>T Max(T a,T b){return a>b?a:b;}template<typename T,typename...Args>T Max(T a,Args...args){return a>Max(args...)?a:Max(args...);}
template<typename T>T Min(T a,T b){return a<b?a:b;}template<typename T,typename...Args>T Min(T a,Args...args){return a<Min(args...)?a:Min(args...);}

namespace io{const int __SIZE=(1<<21)+1;char ibuf[__SIZE],*iS,*iT,obuf[__SIZE],*oS=obuf,*oT=oS+__SIZE-1,__c,qu[55];int __f,qr,_eof;
#define Gc()(iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,__SIZE,stdin),(iS==iT?EOF:*iS++)):*iS++)
	inline void flush(){fwrite(obuf,1,oS-obuf,stdout),oS=obuf;}inline void gc(char&x){x=Gc();}inline void pc(char x){*oS++=x;if(oS==oT)flush();}inline void pstr(const char*s){int __len=strlen(s);for(__f=0;__f<__len;++__f)pc(s[__f]);}inline void gstr(char*s){for(__c=Gc();__c<32||__c>126||__c==' ';)__c=Gc();for(;__c>31&&__c<127&&__c!=' '&&__c!='\n'&&__c!='\r';++s,__c=Gc())*s=__c;*s=0;}template<class I>inline bool gi(I&x){_eof=0;for(__f=1,__c=Gc();(__c<'0'||__c>'9')&&!_eof;__c=Gc()){if(__c=='-')__f=-1;_eof|=__c==EOF;}for(x=0;__c<='9'&&__c>='0'&&!_eof;__c=Gc())x=x*10+(__c&15),_eof|=__c==EOF;x*=__f;return!_eof;}template<class I>inline void print(I x){if(!x)pc('0');if(x<0)pc('-'),x=-x;while(x)qu[++qr]=x%10+'0',x/=10;while(qr)pc(qu[qr--]);}struct Flusher_{~Flusher_(){flush();}}io_flusher_;}using io::pc;using io::gc;using io::pstr;using io::gstr;using io::gi;using io::print;

template<typename T>ostream&operator<<(ostream&os,const vector<T>&v){os<<"{ ";string sep;for(const auto&x:v)os<<sep<<x,sep=", ";return os<<" }";}
template<typename T,size_t size>ostream&operator<<(ostream&os,const array<T,size>&arr){os<<"{ ";string sep;for(const auto&x:arr)os<<sep<<x,sep=", ";return os<<" }";}
template<typename A,typename B>ostream&operator<<(ostream&os,const pair<A,B>&p){return os<<'('<<p.first<<","<<p.second<<')';}
template<typename K,typename V>ostream&operator<<(ostream&os,const map<K,V>&m){os<<"{ ";string sep;for(const auto&p:m)os<<sep<<p.first<<":"<<p.second,sep=", ";return os<<" }";}
template<typename T>ostream&operator<<(ostream&os,const set<T>&s){os<<"{ ";string sep;for(const auto&x:s)os<<sep<<x,sep=", ";return os<<" }";}
template<typename T>ostream&operator<<(ostream&os,const multiset<T>&s){os<<"{ ";string sep;for(const auto&x:s)os<<sep<<x,sep=", ";return os<<" }";}
namespace detail{template<typename T>constexpr bool is_string_type_v=std::is_same_v<std::decay_t<T>,std::string>||std::is_same_v<std::decay_t<T>,const char*>||std::is_same_v<std::decay_t<T>,char*>;template<typename T>void print_val(const T&val){if constexpr(is_string_type_v<T>){std::cerr<<'"'<<val<<'"';}else{std::cerr<<val;}}inline std::string_view trim(std::string_view sv){sv.remove_prefix(std::min(sv.find_first_not_of(" \t"),sv.size()));size_t end=sv.find_last_not_of(" \t");if(end!=std::string_view::npos){sv.remove_suffix(sv.size()-end-1);}return sv;}template<typename...Args>void dbgg_impl(int line,const char*msg,const char*raw_names,Args&&...args){std::cerr<<"Line "<<line<<": "<<msg;if constexpr(sizeof...(Args)>0){if(strlen(msg)>0)std::cerr<<" | ";std::string_view names(raw_names);size_t arg_idx=0;([&]{if(arg_idx>0)std::cerr<<", ";size_t comma_pos=names.find(',');std::string_view current_name=(comma_pos==std::string_view::npos)?names:names.substr(0,comma_pos);std::cerr<<trim(current_name)<<"=";print_val(args);if(comma_pos!=std::string_view::npos){names.remove_prefix(comma_pos+1);}arg_idx++;}(),...);}std::cerr<<std::endl;}}
#ifdef LOCAL_ZCZ
#define dbg(Msg,...)detail::dbgg_impl(__LINE__,Msg,#__VA_ARGS__,##__VA_ARGS__)
#else
#define dbg(...)
#endif

namespace Zhchz{
#define lowbit(x) ((x)&(-(x)))
	constexpr int N=400010,inf=0x3f3f3f3f,base=389,mod=10007;
	constexpr ll INF=0x3f3f3f3f3f3f3f3f;
	constexpr ll INFF=0x7f7f7f7f7f7f7f7f;
	int K,m;
	int pw[N];
	
	int qpow(int a,int b){
		int res=1;
		while(b){
			if(b&1) res=res*a%(mod*m);
			b>>=1;
			a=a*a%(mod*m);
		}
		return res;
	}
	
	int get_111(int len){
		int a=1,res=0;
		int cnt=0;
		while(len){
//			dbg("",len);
			if(len&1){
				res=res*pw[cnt]%(mod*m)+a;
				res%=(mod*m);
			}
			a=a+a*pw[cnt];
			a%=(mod*m);
			cnt++;
			len>>=1;
		}
		return res;
	}
	
	pii add_digit(pii o,int num,int cnt){
		o.fi*=qpow(10,cnt);
		int rem=o.se*qpow(10,cnt)%(mod*m)+num*get_111(cnt)%(mod*m);
		o.fi=(o.fi+rem/m)%mod;
		o.se=rem%m;
		return o;
	}
	
	signed main(){
#ifdef LOCAL_ZCZ
		
#else
		ios::sync_with_stdio(0);
		cin.tie(0), cout.tie(0);
#endif
		cin>>K>>m;
		pw[0]=10;
		for(int i=1;i<=100;i++){
			pw[i]=pw[i-1]*pw[i-1]%(mod*m);
		}
		pii ans={0,0};
		while(K--){
			int c,l;cin>>c>>l;
			ans=add_digit(ans,c,l);
		}
		cout<<ans.fi;
		return 0;
	}
}
signed main(){return Zhchz::main();}

提出情報

ジャッジ結果