結果
問題 |
No.2017 Mod7 Parade
|
ユーザー |
|
提出日時 | 2025-07-12 19:31:09 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 666 ms / 2,000 ms |
コード長 | 4,813 bytes |
コンパイル時間 | 4,825 ms |
コンパイル使用メモリ | 296,084 KB |
実行使用メモリ | 50,944 KB |
最終ジャッジ日時 | 2025-07-12 19:31:24 |
合計ジャッジ時間 | 12,488 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
#include<bits/stdc++.h> #if __has_include(<atcoder/all>) #include<atcoder/modint> #endif using namespace std; #define LL(...) ll __VA_ARGS__;lin(__VA_ARGS__) #define RDVV(T,n,...) vec<T>__VA_ARGS__;fe(refs(__VA_ARGS__),e)e.get().resizes(n);vin(__VA_ARGS__) #define VV(n,...) RDVV(ll,n,__VA_ARGS__) #define FO(n) for(ll IJK=n;IJK-->0;) #define fo(i,...) for(auto[i,i##stop,i##step]=for_range(0,__VA_ARGS__);i<i##stop;i+=i##step) #define fe(a,e,...) for(auto&&__VA_OPT__([)e __VA_OPT__(,__VA_ARGS__]):a) #define defpp void pp(const auto&...a){const char*c="";((cout<<c<<a,c=" "),...);cout<<'\n';} #define entry defpp void main();void main2();}int main(){my::io();my::main();}namespace my{ #define use_ml1000000007 using ml=atcoder::modint1000000007; namespace my{ auto&operator<<(ostream&o,const atcoder::modint1000000007&x){return o<<(int)x.val();} void io(){cin.tie(nullptr)->sync_with_stdio(0);cout<<fixed<<setprecision(15);} using ll=long long; using i64=int64_t; using ui64=uint64_t; using ui128=__uint128_t; constexpr auto refs(auto&...a){return array{ref(a)...};} constexpr auto for_range(ll s,ll b){ll a=0;if(s)swap(a,b);return array{a-s,b,1-s*2};} void lin(auto&...a){(cin>>...>>a);} void vin(auto&...a){fo(i,(a.size()&...))(cin>>...>>a[i]);} constexpr ll size2(auto x){x|=1;ll r=0;while(x>0)x>>=1,++r;return r;} auto&rev(auto&a){ranges::reverse(a);return a;} template<class...A>using pack_back_t=tuple_element_t<sizeof...(A)-1,tuple<A...>>; } namespace my{ template<class V>concept vectorial=is_base_of_v<vector<typename remove_cvref_t<V>::value_type>,remove_cvref_t<V>>; template<class V>constexpr int depth=0; template<vectorial V>constexpr int depth<V> =depth<typename V::value_type>+1; template<class T>struct core_t_helper{using type=T;}; template<vectorial V>struct core_t_helper<V>{using type=typename core_t_helper<typename V::value_type>::type;}; template<class T>using core_t=core_t_helper<T>::type; template<class V>struct vec; template<int D,class T>struct hvec_helper{using type=vec<typename hvec_helper<D-1,T>::type>;}; template<class T>struct hvec_helper<0,T>{using type=T;}; template<int D,class T>using hvec=hvec_helper<D,T>::type; template<class V>struct vec:vector<V>{ static constexpr int D=depth<vec<V>>; using C=core_t<V>; using vector<V>::vector; vec(const auto&...a)requires(sizeof...(a)>=3){resizes(a...);} void resizes(const auto&...a){if constexpr(sizeof...(a)==D)*this=make(a...,C{});else*this=make(a...);} static auto make(ll n,const auto&...a){ if constexpr(sizeof...(a)==1)return vec<C>(n,array{a...}[0]); else return vec<decltype(make(a...))>(n,make(a...)); } ll size()const{return vector<V>::size();} }; template<class...A>requires(sizeof...(A)>=2)vec(const A&...a)->vec<hvec<sizeof...(A)-2,pack_back_t<A...>>>; vec(ll)->vec<ll>; } namespace my{ template<int tag>struct montgomery64{ using modular=montgomery64; static inline ui64 N=998244353; static inline ui64 N_inv=996491785301655553ull; static inline ui64 R2=299560064; static int set_mod(ui64 N){ if(modular::N==N)return 0; assert(N<(1ull<<63)); assert(N&1); modular::N=N; R2=-ui128(N)%N; N_inv=N; FO(5)N_inv*=2-N*N_inv; assert(N*N_inv==1); return 0; } ui64 a; montgomery64(const i64&a=0):a(reduce((ui128)(a%(i64)N+N)*R2)){} static ui64 reduce(const ui128&T){ui128 r=(T+ui128(ui64(T)*-N_inv)*N)>>64;return r>=N?r-N:r;} auto&operator+=(const modular&b){if((a+=b.a)>=N)a-=N;return*this;} auto&operator*=(const modular&b){a=reduce(ui128(a)*b.a);return*this;} friend auto operator+(const modular&a,const modular&b){return modular{a}+=b;} friend auto operator*(const modular&a,const modular&b){return modular{a}*=b;} ui64 val()const{return reduce(a);} }; } namespace my{ template<class T>struct pow_doubling:vec<T>{ pow_doubling(T a,ll n):vec<T>(n+1,a){fo(i,n)(*this)[i+1]=(*this)[i]*(*this)[i];} T operator()(ll k)const{ T res=1; fo(i,size2(k))if(k>>i&1)res*=(*this)[i]; return res; } }; template<class T>struct pow10_doubling:pow_doubling<T>{ vec<T>repunit_table; pow10_doubling(ll n):pow_doubling<T>(10,n),repunit_table(n+2,1){fo(i,n+1)repunit_table[i+1]=((*this)[i]+1)*repunit_table[i];} T repunit(ll k)const{ T res=0; fo(i,size2(k))if(k>>i&1)res=res*(*this)[i]+repunit_table[i]; return res; } }; } namespace my{entry void main(){ LL(N); VV(N,D,L); rev(D); rev(L); ll P=7; using modP=montgomery64<__COUNTER__>; modP::set_mod(P); pow10_doubling<modP>pow10(30); use_ml1000000007 vec dp(N+1,P-1,P,ml{}); dp[0][0][0]=1; fo(i,N){ fo(j,P-1){ fo(k,P){ dp[i+1][j][k]+=dp[i][j][k]; dp[i+1][(j+L[i])%(P-1)][(pow10.repunit(L[i])*D[i]*pow10(j)+k).val()]+=dp[i][j][k]; } } } ml ans=0; fo(j,P-1)fo(k,P)ans+=dp[N][j][k]*k; pp(ans); }}