結果
問題 | No.528 10^9と10^9+7と回文 |
ユーザー |
![]() |
提出日時 | 2017-06-09 23:18:36 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 13 ms / 1,000 ms |
コード長 | 5,583 bytes |
コンパイル時間 | 998 ms |
コンパイル使用メモリ | 106,916 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-23 18:28:22 |
合計ジャッジ時間 | 2,112 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
#include <string>#include <vector>#include<iostream>#include<cstdio>#include<cstdlib>#include<stack>#include<queue>#include<cmath>#include<algorithm>#include<functional>#include<list>#include<deque>#include<bitset>#include<set>#include<map>#include<unordered_map>#include<unordered_set>#include<cstring>#include<sstream>#include<complex>#include<iomanip>#include<numeric>#include<cassert>#define X first#define Y second#define pb push_back#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))#define peat(X,Y) for (;(X) < (Y);++(X))#define all(X) (X).begin(),(X).end()#define rall(X) (X).rbegin(),(X).rend()#define eb emplace_back#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())#define Endl endlusing namespace std;typedef long long ll;typedef pair<int,int> pii;typedef pair<ll,ll> pll;template<class T> using vv=vector<vector<T>>;template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"<<endl; return os;}template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}#define out(args...){vector<string> a_r_g_s=s_p_l_i_t(#args, ','); e_r_r(a_r_g_s.begin(), args); }vector<string> s_p_l_i_t(const string &s, char c){vector<string> v;int d=0,f=0;string t;for(char c:s){if(!d&&c==',')v.pb(t),t="";else t+=c;if(c=='\"'||c=='\'')f^=1;if(!f&&c=='(')++d;if(!f&&c==')')--d;}v.pb(t);return move(v);}void e_r_r(vector<string>::iterator it) {}template<typename T, typename... Args> void e_r_r(vector<string>::iterator it, T a, Args... args){ if(*it==" 1"||*it=="1") cerr<<endl; else cerr <<it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << ", "; e_r_r(++it, args...);}const ll MOD=1e9+7;ll modpow(ll r,ll n,ll m=MOD){ll re=1,d=r%m;if(n<0)(n%=m-1)+=m-1;for(;n;n/=2){if(n&1)(re*=d)%=m;(d*=d)%=m;}return re;}template <int mod=MOD> struct modInt{int v;modInt(int v=0):v(v){}modInt operator+(const modInt &n){return v+n.v<mod ? v+n.v : v+n.v-mod;}modInt operator-(const modInt &n){return v-n.v<0 ? v-n.v+mod : v-n.v;}modInt operator*(const modInt &n){return ll(v)*n.v%mod;}modInt operator/(const modInt &n){return ll(v)*modpow(n.v%mod,-1,mod)%mod;}template<class T> modInt operator+(const T &n){return v+n<mod ? v+n : v+n-mod;}template<class T> modInt operator-(const T &n){return v-n<0 ? v-n+mod : v-n;}template<class T> modInt operator*(const T &n){return ll(v)*(n%mod)%mod;}template<class T> modInt operator/(const T &n){return ll(v)*modpow(n%mod,-1,mod)%mod;}modInt& operator+=(const modInt &n){v+=n.v; if(v>=mod) v-=mod; return *this;}modInt& operator-=(const modInt &n){v-=n.v; if(v<0) v+=mod; return *this;}modInt& operator*=(const modInt &n){v=ll(v)*n.v%mod; return *this;}modInt& operator/=(const modInt &n){v=ll(v)*modpow(n.v,-1,mod)%mod; return *this;}template<class T> modInt& operator+=(const T &n){v+=n; if(v>=mod) v-=mod; return *this;}template<class T> modInt& operator-=(const T &n){v-=n; if(v<0) v+=mod; return *this;}template<class T> modInt& operator*=(const T &n){v=ll(v)*n%mod; return *this;}template<class T> modInt& operator/=(const T &n){v=ll(v)*modpow(n,-1,mod)%mod; return *this;}};template<int mod> ostream& operator<<(ostream &os,const modInt<mod> &n){return os<<n.v;};template<class T,int mod> modInt<mod> operator+(const T &n,const modInt<mod> &m){return m.v+n<mod ? m.v+n : m.v+n-mod;}template<class T,int mod> modInt<mod> operator-(const T &n,const modInt<mod> &m){return n-m.v<0 ? n-m.v+mod : n-m.v;}template<class T,int mod> modInt<mod> operator*(const T &n,const modInt<mod> &m){return ll(m.v)*(n%mod)%mod;}template<class T,int mod> modInt<mod> operator/(const T &n,const modInt<mod> &m){return ll(m.v)*modpow(n%mod,-1,mod)%mod;}typedef modInt<MOD> mint;typedef modInt<1000000000> Mint;template <int mod> modInt<mod> modpow(modInt<mod> r,ll n){ modInt<mod> re(1); if(n<0)(n%=mod-1)+=mod-1; for(;n;n/=2){if(n&1) re*=r; r*=r;} return re;}vector<mint> fact,finv,inv;mint comb(ll n,ll r){ if(n<r||r<0)return 0; return fact[n]*finv[n-r]*finv[r];}class Doralion{void Modinvs(vector<mint> &re,int n){ re.resize(n+1); re[1]=1; for(int i=2;i<=n;++i)re[i]=re[MOD%i]*(MOD-MOD/i);}void Facts(vector<mint> &re,int n){ re.resize(n+1); re[0]=1; rep(i,n)re[i+1]=re[i]*(i+1);}void Factinvs(vector<mint> &re,const vector<mint> &inv,int n){ re.resize(n+1); re[0]=1; rep(i,n)re[i+1]=re[i]*inv[i+1];}public:Doralion(int n){ Modinvs(inv,n); Facts(fact,n); Factinvs(finv,inv,n);}} doralion(212345);int main(){ios_base::sync_with_stdio(false);cout<<fixed<<setprecision(0);string s;cin>>s;assert(s[0]!='0');int n=s.size();mint re=0;Mint ret=0;vector<mint> pw(112345); pw[0]=1;vector<Mint> pwr(112345); pwr[0]=1;rep(i,102345) pw[i+1]=pw[i]*10, pwr[i+1]=pwr[i]*10;reps(i,1,n){re+=pw[(i+1)/2-1]*9;ret+=pwr[(i+1)/2-1]*9;}//out(re,ret,1);int m=(n+1)/2;rep(i,m){re+=max(0,s[i]-'0'-!i)*pw[m-1-i];ret+=max(0,s[i]-'0'-!i)*pwr[m-1-i];}string t=s;reps(i,m,n) t[i]=s[n-1-i];//out(s,1,t,1);if(s>=t) re+=1, ret+=1;cout<<ret<<endl<<re<<endl;return 0;}