1422C - Bargain - CodeForces Solution


combinatorics dp math *1700

Please click on ads to support us..

Python Code:

import gc
import heapq
import itertools
import math
import sqlite3
from collections import Counter, deque, defaultdict
from sys import stdout
import time
from math import factorial, log, gcd
import sys
from decimal import Decimal
import threading
from heapq import *
from fractions import Fraction


def S():
    return sys.stdin.readline().split()


def I():
    return [int(i) for i in sys.stdin.readline().split()]


def II():
    return int(sys.stdin.readline())


def IS():
    return sys.stdin.readline().replace('\n', '')


def is_prime(n):
    for i in range(2, int(n ** 0.5) + 2):
        if n % i == 0 and i < n:
            return False
    return True


def main():
    n = IS()
    _len = len(n)
    c = [(_len * (_len - 1) // 2) % mod, 0]
    tan = 1
    ans = 0
    for i in range(_len - 1, -1, -1):
        ans = (ans + (c[0] * pow(10, (_len - i - 1), mod) + c[1]) * int(n[i])) % mod
        c[0] = (c[0] - i) % mod
        c[1] = (c[1] + tan * (_len - i)) % mod
        tan = (tan * 10) % mod

    print(ans % mod)



if __name__ == '__main__':
    mod = 10 ** 9 + 7
            main()

C++ Code:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf (ll)1e18
#define pi (3.141592653589)
ll mod=1000000007;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define min3(a, b, c) min(c, min(a, b))
#define min4(a, b, c, d) min(d, min(c, min(a, b)))
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
vector<ll>adj[200002];
vector<ll>vis(200002,0);
vector<ll>dis(200002,0);
#define countbit(a) __builtin_popcount(a)
void extendgcd(ll a, ll b, ll*v) {if (b == 0) {v[0] = 1; v[1] = 0; v[2] = a; return ;} extendgcd(b, a % b, v); ll x = v[1]; v[1] = v[0] - v[1] * (a / b); v[0] = x; return;} //pass an arry of size1 3
ll expo(ll a, ll b, ll mod) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
ll mminv(ll a, ll b) {ll arr[3]; extendgcd(a, b, arr); return arr[0];} //for non prime b
ll mminvprime(ll a, ll b) {return expo(a, b - 2, b);}  //for prime b
//void google(int t) {cout << Case # << t << : ;}
#define all(v) v.begin(),v.end()
/*returns nCr*/ll combination(ll n, ll r, ll m, ll *fact, ll *ifact) {ll val1 = fact[n]; ll val2 = ifact[n - r]; ll val3 = ifact[r]; return (((val1 * val2) % m) * val3) % m;}
#define vll vector<ll>
#define pll pair<ll,ll>
#define dec(n) cout<<fixed; cout<<setprecision(n);
ll dp1[1030][1020];
ll C(int n, int r){ if (r == 0 || r == n) return 1; if (dp1[n][r]) return dp1[n][r];return dp1[n][r] = (C(n - 1, r - 1) + C(n - 1, r)) % mod;}
/*ll up[200002][20];
ll depth[200002];
ll LCA(ll x,ll y){if(depth[x]>depth[y]) swap(x,y); ll d= depth[y]-depth[x];  for(int i=19;i>=0;i--){ if(d&(1<<i)) {y=up[y][i];}}if(x==y) return x; for(int i=19;i>=0;i--) {if(up[x][i]!=up[y][i]){x=up[x][i];y=up[y][i];}}return up[x][0];}
void LCAprec(ll node){vis[node]=1;for(auto x:adj[node]){if(vis[x]==0){depth[x]=depth[node]+1;up[x][0]=node;for(int i=1;i<20;i++){up[x][i]=up[up[x][i-1]][i-1];}LCAprec(x);}}}
*/

int main()
{
fast
int t=1;
//cin>>t;
for(int tc=1;tc<=t;tc++)
{
    string s;
    cin>>s;
    ll n=s.size();
    ll cur=0;
    ll ans=0;
    vector<ll>dp(n+1,1);
    for(int i=1;i<=n;i++)
    {
        dp[i]=(expo(10,i,mod)+dp[i-1])%mod;
    }
    for(int i=0;i<n;i++)
    {
        cur=(10*cur+(s[i]-'0'))%mod;
        ll d=n-i-1;
        if(d-1>=0)
        ans+=(cur*dp[d-1])%mod;
        //cout<<ans<<" ";
        ans%=mod;
    }
    cur=0;
    for(int i=n-1;i>=1;i--)
    {
        cur=cur+(s[i]-'0')*expo(10,n-i-1,mod);
        cur%=mod;
        ans+=(cur*(i))%mod;
        ans%=mod;
    }
    cout<<ans<<'\n';
}


}


Comments

Submit
0 Comments
More Questions

Cutting a material
Bubble Sort
Number of triangles
AND path in a binary tree
Factorial equations
Removal of vertices
Happy segments
Cyclic shifts
Zoos
Build a graph
Almost correct bracket sequence
Count of integers
Differences of the permutations
Doctor's Secret
Back to School
I am Easy
Teddy and Tweety
Partitioning binary strings
Special sets
Smallest chosen word
Going to office
Color the boxes
Missing numbers
Maximum sum
13 Reasons Why
Friend's Relationship
Health of a person
Divisibility
A. Movement
Numbers in a matrix