結果
問題 | No.1580 I like Logarithm! |
ユーザー | kaiser l |
提出日時 | 2021-09-20 23:44:33 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 3,244 bytes |
コンパイル時間 | 7,921 ms |
コンパイル使用メモリ | 411,496 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-03 01:13:18 |
合計ジャッジ時間 | 9,381 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,944 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 3 ms
6,944 KB |
testcase_07 | AC | 5 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,944 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 2 ms
6,944 KB |
testcase_11 | AC | 4 ms
6,940 KB |
testcase_12 | AC | 3 ms
6,944 KB |
testcase_13 | AC | 3 ms
6,940 KB |
testcase_14 | AC | 5 ms
6,940 KB |
testcase_15 | AC | 4 ms
6,944 KB |
testcase_16 | AC | 2 ms
6,944 KB |
testcase_17 | AC | 2 ms
6,944 KB |
testcase_18 | AC | 2 ms
6,940 KB |
testcase_19 | AC | 2 ms
6,940 KB |
testcase_20 | AC | 2 ms
6,944 KB |
testcase_21 | AC | 2 ms
6,944 KB |
testcase_22 | AC | 2 ms
6,940 KB |
testcase_23 | AC | 2 ms
6,940 KB |
testcase_24 | AC | 2 ms
6,940 KB |
testcase_25 | AC | 2 ms
6,940 KB |
testcase_26 | AC | 4 ms
6,940 KB |
testcase_27 | AC | 4 ms
6,940 KB |
testcase_28 | AC | 5 ms
6,944 KB |
testcase_29 | AC | 4 ms
6,940 KB |
testcase_30 | AC | 5 ms
6,940 KB |
testcase_31 | AC | 5 ms
6,940 KB |
testcase_32 | AC | 4 ms
6,940 KB |
testcase_33 | AC | 4 ms
6,940 KB |
testcase_34 | AC | 5 ms
6,944 KB |
testcase_35 | AC | 5 ms
6,940 KB |
testcase_36 | AC | 4 ms
6,944 KB |
testcase_37 | AC | 4 ms
6,940 KB |
testcase_38 | AC | 5 ms
6,944 KB |
testcase_39 | AC | 5 ms
6,940 KB |
testcase_40 | AC | 4 ms
6,940 KB |
testcase_41 | AC | 5 ms
6,940 KB |
testcase_42 | AC | 5 ms
6,940 KB |
testcase_43 | AC | 5 ms
6,944 KB |
testcase_44 | AC | 5 ms
6,940 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; #include <boost/multiprecision/cpp_int.hpp> #include <boost/multiprecision/number.hpp> using namespace boost::multiprecision; using mint=modint1000000007; #define tpf typedef tpf double db;tpf long long ll; tpf string str;tpf vector<ll> vll; tpf vector<str> vs;tpf pair<ll,ll> pll; tpf vector<pll> vpll;tpf vector<vll> vvll; tpf cpp_int cp;tpf complex<db> com; tpf vector<bool> vb; int a,b; #define For(i,a,b) for(int i=(a);i<(b);++i) #define rep(i,n) For(i,0,n) #define F first #define S second #define psf push_front #define psb push_back #define epb emplace_back #define mkp make_pair #define All(x) x.begin(),x.end() #define Alld(x) All(x),greater<>() #define dupde(x) x.erase(unique(All(x)),x.end()) #define nxp next_permutation #define sep setprecision #define lob lower_bound const int mod = 1000000007;const ll INF=1e17; const db pi=acos(-1); const int di[]={-1,0,1,0}; const int dj[]={0,-1,0,1}; ll gcd(ll x,ll y){return y? gcd(y,x%y):x;} ll ncr(ll n,ll r){ ll x=1,y=1;rep(i,r){x*=(n-i);y*=(i+1);} return x/y; } mint modncr(ll n,ll r){ mint x=1,y=1;r=min(n-r,r); rep(i,r){x*=(n-i);y*=(i+1);} return x*y.inv(); } ll pncr(ll n,ll r){ vvll v(n+1,vll(n+1));v[0][0]=1; rep(i,n)rep(j,i+1){ v[i+1][j]+=v[i][j]; v[i+1][j+1]+=v[i][j]; } return v[n][r]; } template<class T> inline bool chmin(T& a, T b){ if(a>b){a=b;return true;}return false; } template<class T> inline bool chmax(T& a, T b){ if(a<b){a=b;return true;}return false; } ll to_base(ll n,ll i){ string s; while(n){s=to_string(n%i)+s;n/=i;} ll a=stoll(s);return a; } ll prime(ll n){ if(n==2)return 1; if(n%2==0||n==1)return 0; for(ll i=3;i*i<=n;i+=2)if(n%i==0)return 0; return 1; } vll divisor(ll n){ vll a; for(ll i=1;i*i<=n;i++){ if(n%i==0){ a.psb(i);if(i!=n/i)a.psb(n/i); } } sort(All(a));return a; } vector<pair<ll,ll>> prifac(ll n){ vector<pair<ll,ll>> a; for(ll i=2;i*i<=n;i++){ if(n%i!=0){continue;}ll exp=0; while(n%i==0){n/=i;exp++;} a.psb(pll(i,exp)); } if(n!=1){a.psb(pll(n,1));}return a; } vll cumsum(vll a){ ll sz=a.size(); vll dp(sz+1); rep(i,sz)dp[i+1]=dp[i]+a[i]; return dp; } vll eratos(ll n){ vll f(n+1),p; rep(i,n+1)f[i]=1; For(i,2,n+1){ if(f[i]){ for(ll j=2*i;j<=n;j+=i)f[j]=0; p.psb(i); } } return p; } vll eratos2(vll a,ll n){ vb x(n),ok(n,true);vll p,res; for(ll i:a)x[i]=true; For(i,2,n){ bool f=false; for(ll j=i;j<n;j+=i)if(x[j])f=true; if(f)p.psb(i); } for(ll i:p){ for(ll j=i;j<n;j+=i){ ok[j]=false; } } For(i,1,n)if(ok[i])res.psb(i); return res; } ll eulerf(ll n){ vll v(1);v[0]=n; vll res=eratos2(v,n+1); return res.size(); } ll eulerf2(ll n){ vpll a=prifac(n);ll res=n; for(auto i:a){res*=i.F-1;res/=i.F;} return res; } int main(){ ios::sync_with_stdio(0); cin.tie(0); ll a,ans=0,c=0;str b;cin>>a>>b; ll n=b.size(); vll v(n);reverse(All(b)); v[0]=1;n%=mod; rep(i,n-1){ v[i+1]=v[i]*a%mod; } rep(i,n){ c+=v[i]*(b[i]-'0')%mod; c%=mod; } For(i,1,n){ ans+=(i-1)*(v[i]-v[i-1])%mod; ans%=mod; } ans+=(n-1)*(c-v[n-1]+1)%mod; cout<<(ans+2*mod)%mod; return 0; }