結果
| 問題 | No.3022 一元一次式 mod 1000000000 |
| ユーザー |
 clever-elsie
|
| 提出日時 | 2025-03-18 22:44:32 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 15,743 bytes |
| コンパイル時間 | 2,875 ms |
| コンパイル使用メモリ | 227,336 KB |
| 実行使用メモリ | 7,328 KB |
| 最終ジャッジ日時 | 2025-03-18 22:44:38 |
| 合計ジャッジ時間 | 4,631 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 8 WA * 13 |
ソースコード
#ifndef ELSIE_LOCAL_H#define ELSIE_LOCAL_H#ifndef ELSIE_MISC_HEADER#define ELSIE_MISC_HEADER#if __has_include(<atcoder/modint>)#include "atcoder/modint"using namespace atcoder;using mint=modint998244353;using mint1=modint1000000007;#endif#include <limits>#include <new>#include <initializer_list>#include <compare>#include <concepts>#include <utility>#include <bitset>#include <tuple>#include <type_traits>#include <functional>#include <chrono>#include <array>#include <deque>#include <list>#include <queue>#include <vector>#include <set>#include <map>#include <unordered_map>#include <unordered_set>#include <iterator>#include <ranges>#include <algorithm>#include <bit>#include <random>#include <numeric>#include <numbers>#include <iostream>#include <ios>#include <streambuf>#include <iomanip>#include <sstream>#include <regex>#include <cassert>#include <cctype>#include <climits>#include <cmath>#include <cstdarg>#include <cstddef>#include <cstdint>#include <cstdio>#include <cstdlib>#include <cstring>#include <ctime>using namespace std;using namespace chrono;using std::cin;using std::cout;using sstream=stringstream;#endif#ifndef ELSIE_MISC_DEFINE#define ELSIE_MISC_DEFINE#define RET return#define fi first#define se second#define endl '\n'#define sn(i,c) " \n"[i==c]#define rsv(n) reserve(n)#define pf(a) push_front(a)#define pb(a) push_back(a)#define eb(...) emplace_back(__VA_ARGS__)#define ppf() pop_front()#define ppb() pop_back()#define pp() pop()#define ins(a) insert(a)#define emp(...) emplace(__VA_ARGS__)#define ers(a) erase(a)#define cont(a) contains(a)#define mp(f,s) make_pair(f,s)#define A(a) begin(a),end(a)#define I(a,i) begin(a),begin(a)+(i)#define _SEL4(_1,_2,_3,_4,name,...) name#define _SEL3(_1,_2,_3,name,...) name#define _REP4(i,s,n,st) for(long i=(s);i<(n);i+=(st))#define _REP3(i,s,n) _REP4(i,s,n,1)#define _REP2(i,n) _REP3(i,0,n)#define _REP1(n) _REP2(_,n)#define _RREP4(i,n,t,s) for(long i=(n);i>=(t);i-=(s))#define _RREP3(i,n,t) _RREP4(i,n,t,1)#define _RREP2(i,n) _RREP3(i,n,0)#define _ITER2(x,a) for(auto&&x:a)#define _ITER3(x,y,a) for(auto&&[x,y]:a)#define _CTER2(x,a) for(const auto&x:a)#define _CTER3(x,y,a) for(const auto&[x,y]:a)#define rep(...) _SEL4(__VA_ARGS__,_REP4,_REP3,_REP2,_REP1)(__VA_ARGS__)#define rrep(...) _SEL4(__VA_ARGS__,_RREP4,_RREP3,_RREP2,_REP1)(__VA_ARGS__)#define iter(...) _SEL3(__VA_ARGS__,_ITER3,_ITER2)(__VA_ARGS__)#define cter(...) _SEL3(__VA_ARGS__,_CTER3,_CTER2)(__VA_ARGS__)#endif#ifndef ELSIE_MISC_CONST#define ELSIE_MISC_CONST#define NL cout<<'\n'#define npi numbers::piconstexpr int64_t inf=1ll<<60,minf=-inf;constexpr int32_t inf32=1ll<<30,minf32=-inf32;constexpr char sep='\n';constexpr array<pair<int32_t,int32_t>,8>dc={{{1,0},{0,1},{-1,0},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}}};#define yes cout<<"Yes\n"#define no cout<<"No\n"#define yn(c) (c)?yes:no#endif#if __cplusplus > 202002L#ifndef ELSIE_MISC_FUNC#define ELSIE_MISC_FUNCnamespace vies=std::views;#define DR(i) views::drop(i)#define TK(i) views::take(i)#define RV views::reverse#define IOTA vies::iota#define rev(a) reverse(A(a))#define minel(a) min_element(A(a))#define maxel(a) max_element(A(a))#define acm(a) accumulate(A(a),0ll)#define nxpm(a) next_permutation(A(a))#define Sort(a) sort(A(a))#define uni(a) Sort(a);a.erase(unique(A(a)),a.end())#define swapcase(a) a=(isalpha(a)?a^32:a)template<class T,class U>inline void chmax(T&a,const U&b){if(a<b)a=b;}template<class T,class U>inline void chmin(T&a,const U&b){if(a>b)a=b;}#define _BISECT4(_1,_2,_3,_4,name,...) name#define _LB_BEX(b,e,x) lower_bound(b,e,x)#define _LB_BEXG(b,e,x,g) lower_bound(b,e,x,g)#define _UB_BEX(b,e,x) upper_bound(b,e,x)#define _UB_BEXG(b,e,x,g) upper_bound(b,e,x,g)#define lb(...) _BISECT4(__VA_ARGS__,_LB_BEXG,_LB_BEX)(__VA_ARGS__)#define ub(...) _BISECT4(__VA_ARGS__,_UB_BEXG,_UB_BEX)(__VA_ARGS__)#define TP template<class T,class U,typename cp=less<U>>template<class T,class U>concept LUBI= same_as<T,vector<U>>||same_as<T,deque<U>>||is_array_v<T>;#define RL requires LUBI<T,U>TP size_t lbi(const T&v,const U&x,cp cmp=cp())RL{RET lb(A(v),x,cmp)-begin(v);}TP size_t ubi(const T&v,const U&x,cp cmp=cp())RL{RET ub(A(v),x,cmp)-begin(v);}TP size_t lbi(size_t i,const T&v,const U&x,cp cmp=cp())RL{RET lb(i+A(v),x,cmp)-begin(v);}TP size_t ubi(size_t i,const T&v,const U&x,cp cmp=cp())RL{RET ub(i+A(v),x,cmp)-begin(v);}TP size_t lbi(const T&v,size_t i,const U&x,cp cmp=cp())RL{RET lb(I(v,i),x,cmp)-begin(v);}TP size_t ubi(const T&v,size_t i,const U&x,cp cmp=cp())RL{RET ub(I(v,i),x,cmp)-begin(v);}TP size_t lbi(size_t i,const T&v,size_t e,const U&x,cp cmp=cp())RL{RET lb(i+I(v,e),x,cmp)-begin(v);}TP size_t ubi(size_t i,const T&v,size_t e,const U&x,cp cmp=cp())RL{RET ub(i+I(v,e),x,cmp)-begin(v);}#undef TP#undef RL#define TP template<integral T>#define MT make_unsigned_t<T>TP constexpr int32_t pcnt(T p){return popcount(MT(p));}TP constexpr int32_t lsb(T p){return countr_zero(MT(p));}TP constexpr int32_t msb(T p){return sizeof(T)*8-1-countl_zero(MT(p));}template<int32_t N,integral T>void putbit(T s){char buf[N+1]={0};for(char*itr=buf+N-1;itr>=buf;itr--,s>>=1)*itr='0'+(s&1);cout<<buf<<sep;}#undef TP#undef MT#endif#ifndef ELSIE_STD_IO#define ELSIE_STD_IO#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)#define STR(...) str __VA_ARGS__;in(__VA_ARGS__)#define VI(a,n) vi a(n);in(a)#define VIT(a,n) vit a(n);in(a)#define VS(a,n) vs a(n);in(a)#define UV(u,v) INT(u,v);--u,--v#define UVW(u,v,w) INT(u,v,w);--u,--v#ifdef LOCAL#define dput(...) dos=&cerr;out(__VA_ARGS__);dos=&cout#else#define dput(...)#endiftemplate<class T>concept Lint=same_as<T,__int128_t>||same_as<T,__uint128_t>;template<class T>concept Itrabl=requires(const T&x){x.begin();x.end();}&&!std::is_same_v<T,string>;template<class T>concept IItrabl=Itrabl<T>&&Itrabl<typename T::value_type>;template<class T>concept ModInt=requires(const T&x){x.val();};template<class T>concept NLobj=Itrabl<T>||std::is_same_v<T,string>;istream&operator<<(istream&is,__float128&x){double y;is>>y;x=y;return is;}ostream&operator<<(ostream&os,const __float128&x){return os<<static_cast<double>(x);}template<Lint T>ostream&operator<<(ostream&dst,T val){ostream::sentry s(dst);if(!s)return dst;char _O128[64];char*d=end(_O128);bool vsign=val<0;__uint128_t v=val;if(vsign&&val!=numeric_limits<T>::min())v=1+~(__uint128_t)val;do{*(--d)="0123456789"[v%10];v/=10;}while(v!=0);if(vsign)*(--d)='-';ptrdiff_t len=end(_O128)-d;if(dst.rdbuf()->sputn(d,len)!=len)dst.setstate(ios_base::badbit);return dst;}template<Lint T>istream&operator>>(istream&src,T&val) {string s;src>>s;bool is_neg=numeric_limits<T>::is_signed&&s.size()>0&&s[0]=='-';for(val=0;const auto&x:s|views::drop(is_neg))val=10*val+x-'0';if(is_neg)val*=-1;return src;}template<ModInt T>istream&operator>>(istream&is,T&v){int64_t x;is>>x;v=x;return is;}template<class T,class U>istream&operator>>(istream&is,pair<T,U>&v){return is>>v.first>>v.second;}template<Itrabl T>istream&operator>>(istream&is,T&v){for(auto&&x:v)is>>x;return is;}template<class T>void in(T&a){cin>>a;}template<class T,class... Ts>void in(T&a,Ts&... b){in(a);in(b...);}template<class T,class U>vector<pair<T,U>>zip(size_t n,size_t m){vector<pair<T,U>>r(min(n,m));iter(x,y,r)in(x);iter(x,y,r)in(y);return move(r);}template<class T,class U>vector<pair<T,U>>zip(size_t n){return move(zip<T,U>(n,n));}template<ModInt T>ostream&operator<<(ostream&os,const T&v){return os<<v.val(); }template<class T,class U>ostream&operator<<(ostream&os,const pair<T,U>&v){return os<<'('<<v.first<<','<<v.second<<')';}template<Itrabl T>ostream&operator<<(ostream&os,const T&v){size_t cnt=0;cter(x,v)os<<x<<(++cnt<v.size()?" ":"");return os;}template<IItrabl T>ostream&operator<<(ostream&os,const T&v){size_t cnt=0;cter(x,v)os<<x<<(++cnt<v.size()?"\n":"");return os;}inline ostream*dos=&cout;inline int32_t OFLG; // 0:first, 1:notNLobj, 2:NLobjtemplate<class T>void _out(const T&a){if(OFLG)(*dos)<<"0 \n"[OFLG]<<a;else(*dos)<<a;OFLG=1;}template<NLobj T>void _out(const T&a){(*dos)<<(OFLG?"\n":"")<<a;OFLG=2;}template<class T,class...Ts>void _out(const T&a,const Ts&... b){_out(a);_out(b...);}template<class... Ts>void out(const Ts&... v){OFLG=0;_out(v...);(*dos)<<sep;}#endif#endif#endif#ifndef ELSIE_BASIC_MATH#define ELSIE_BASIC_MATHnamespace elsie{using namespace std;using namespace atcoder;template<integral T,integral U>inline auto ceil(const T a,const U b){return(a+b-1)/b;}template<integral T,integral U>inline auto floor(const T a,const U b){return a/b-(a%b&&(a^b)<0);}// std::ceil(std::sqrtl(x:u64))が64bit精度で40%高速なので，long double 80bitならそちらを使うべきtemplate<bool internal_invocate=false>inline uint64_t sqrt_ceil(uint64_t x){if constexpr(!internal_invocate){// sqrt_floorからの呼出しではここをスキップするif(x>uint64_t(UINT32_MAX)*UINT32_MAX)return 1ull<<32;else if(x<2)return x!=0;}uint64_t nx,y=min<uint64_t>((1ULL<<((64-countl_zero(x))>>1)+1)-1,UINT32_MAX);y-=(y*y-x)/(y<<1);y-=(y*y-x)/(y<<1);y-=(y*y-x)/(y<<1);y-=(y*y-x)/(y<<1);y-=(y*y-x)/(y<<1);nx=y-(y*y-x)/(y<<1);while(nx!=y){y=nx;nx=y-(y*y-x)/(y<<1);if(nx==y)break;}return y+(y*y<x?1:(y-1)*(y-1)>=x?-1:0);}inline uint64_t sqrt_floor(uint64_t x){if((uint64_t)UINT32_MAX*UINT32_MAX<=x)return UINT32_MAX;else if(x<4)return x!=0;uint64_t y=sqrt_ceil<true>(x);return y-(y*y!=x);}using u128=__uint128_t;using u64 = uint64_t;inline __uint128_t mul64to128(u64 a,u64 b){u64 hi,lo;asm("mulq %3" :"=a"(lo),"=d"(hi):"a"(a),"r"(b));return((__uint128_t)(hi)<<64)+lo;}inline pair<u128,u128>mul128(u128 a,u128 b){constexpr static u128 Lfilter=0xFFFF'FFFF'FFFF'FFFFull;u64 x1=a>>64,x0=a&Lfilter;u64 y1=b>>64,y0=b&Lfilter;u128 z2=mul64to128(x1,y1),z1=mul64to128(x1,y0)+mul64to128(x0,y1),z0=mul64to128(x0,y0);u128 lower=z0+(z1<<64);return{z2+(z1>>64)+(lower<z0),lower};}inline u128 rem256(pair<u128,u128>x,u128 mod){u128 rem32=(u128(1)<<32)%mod;u128 rem64=rem32*rem32%mod;u128 rem128=rem64*rem64%mod;auto&&[a,b]=x;a%=mod,b%=mod;return(a*rem128%mod+b)%mod;}int64_t safepow(int64_t a,uint64_t b){int64_t ret=1,k=a;double check=1,kcheck=a;while(b){if(b&1){check*=k;if(check>INT64_MAX)return INT64_MAX;if(check<INT64_MIN)return INT64_MIN;ret*=k;}kcheck*=k;if(kcheck>INT64_MAX)return INT64_MAX;if(kcheck<INT64_MIN)return INT64_MIN;k*=k;b>>=1;}return ret;}template<integral T,class U=make_unsigned_t<T>>constexpr T modpow(T a,U b,U mod){if constexpr(is_same_v<U,__uint128_t>){ // mod=2^64専用constexpr __uint128_t filter=uint64_t(-1);a%=mod;__uint128_t ret=1;if(a<0)a+=mod;while(b){ret=(b&1?ret*a&filter:ret);a=a*a&filter;b>>=1;}return uint64_t(ret&filter);}else{__int128_t k=a%mod,ret=1;if(k<0)k+=mod;while(b){ret=(b&1?ret*k%mod:ret);k=(k*k)%mod;b>>=1;}return int64_t(ret);}}template<class S>S gcd(S a,S b){if(b==0) return a;S r=1;if(a<0)a=-a;if(b<0)b=-b;while(r) r=a%b,a=b,b=r;return a;}template<class S>S lcm(S a,S b){return a/gcd(a,b)*b;}template<class S>S egcd(S a,S b,S&x,S&y){if(b==0){x=1,y=0;return a;}S d=egcd(b,a%b,y,x);y-=a/b*x;return d;}template<class T>T exgcd(T a,T b,T&x,T&y){auto assign=[&](T&s,T&t,T u,T v)->void {s=u,t=v;};x=1,y=0;T u=0,v=1;while(b){T k=a/b,r=a%b;assign(a,b,b,r);assign(x,u,u,x-u*k);assign(y,v,v,y-v*k);}if constexpr(is_signed_v<T>)if(a<0)a=-a,x=-x,y=-y;return a;}template<class T>T mod_inv(T a,T m){T x,y,g=exgcd(a,m,x,y);if(g!=1)return -1;return(x%m+m)%m;}template<class T>T mod_inv_prime(T a,T p){ return modpow(a,p-2,p); }template<class mint=modint998244353>class combination{private:using tint = long long;vector<mint>invprod,prod;vector<tint>inv;const unsigned long long M;public:combination(int64_t n=1):invprod(2,1),prod(2,1),inv(2,0),M(mint(-1).val()+1){inv[1]=1;if(n>1)PreCalc(n);}void PreCalc(int64_t n){size_t presize=inv.size();if(presize>=n+1)return;inv.resize(n+1);prod.resize(n+1);invprod.resize(n+1);for(int64_t i=presize;i<=n;++i){prod[i]=prod[i-1]*i;inv[i]=(((M/i)*(-inv[M%i]))+M)%M;invprod[i]=invprod[i-1]*inv[i];}}mint factorial(size_t n){PreCalc(n);return prod[n];}mint invfact(size_t n){PreCalc(n);return invprod[n];}mint P(size_t n,size_t k){if(n<k) return 0;PreCalc(n);return prod[n]*invprod[n-k];}mint C(size_t n,size_t k){if(n<k) return 0;PreCalc(n);return prod[n]*invprod[n-k]*invprod[k];}mint H(size_t n,size_t k){if(n==0) return mint(k!=0);PreCalc(n);return C(n+k-1,k);}};class barret32{uint64_t M,iM;public:barret32():M(0),iM(0){}barret32(uint32_t m):M(m),iM(uint64_t(-1)/m+1){}void set(uint32_t m){ M=m,iM=uint64_t(-1)/m+1; }uint32_t umod()const{ return M; }uint32_t mul(uint32_t a,uint32_t b)const{uint64_t z=(uint64_t)a*b;uint64_t x=((__uint128_t)z*iM>>64);uint64_t y=x*M;return(uint32_t)(z-y+(z<y?M:0));}};class barret64{__uint128_t M,iM;public:barret64():M(0),iM(0){}barret64(uint64_t m):M(m),iM(__uint128_t(-1)/M+1){}uint64_t umod(){ return M; }uint64_t mul(uint64_t a,uint64_t b){__uint128_t z=mul64to128(a,b);__uint128_t x=mul128(z,iM).first;__uint128_t y=x*M;return(uint64_t)(z-y+(z<y?M:0));}};}#endif#ifndef ELSIE_ALIAS#define ELSIE_ALIAStemplate<class f>using vc=vector<f>;template<class f>using vv=vc<vc<f>>;template<class f>using v3=vv<vc<f>>;template<class f>using v4=vv<vv<f>>;template<class f>using gr=greater<f>;template<class f>using pq=priority_queue<f>;template<class f>using pqg=priority_queue<f, vc<f>, gr<f>>;#define uset unordered_set#define umap unordered_mapusing it=int32_t;using i8=int8_t; using u8=uint8_t;using i16=int16_t; using u16=uint16_t;using i32=int32_t; using u32=uint32_t;using i64=int64_t; using u64=uint64_t;using i128=__int128_t; using u128=__uint128_t;using intw=__int128_t; using uintw=__uint128_t;using f32=float;using f64=double;using f128=__float128;using vi=vc<i64>;using vit=vc<it>;using vb=vc<bool>;using pi=pair<i64,i64>;using pit=pair<it,it>;using str=string;using vs=vc<str>;using pqgp=pqg<pi>;#define int i64#define itn i64#define LL long long#endifvoid slv(){constexpr int s=1'000'000'000;INT(n,m);n%=s;m%=s;if(m)m=s-m;int k=elsie::mod_inv(n,s);if(k==-1)out(k);else out(m*k%s);}signed main(){cin.tie(0)->sync_with_stdio(0);cout<<fixed<<setprecision(15);INT(t);rep(t) slv();}