HackerRank Weekly Challenges - Week 3 2問目 - Sam and sub-strings

Source

HackerRank Weekly Challenges - Week 3 2問目
problem statement（コンテストページ）
problem statement

問題概要

長さ $N$ の数字からなる文字列 $S$ が与えられる．
$S$ の各部分文字列を $10$ 進数の整数とみなして，$S$ の全ての部分文字列が表す整数の和を ${\rm mod}\ 1000000007\ (10^9+7)$ で求める問題．
部分文字列を考えるさい，先頭が $\verb|0|$ の部分文字列も許容する．

解法

$11 \cdots 1$ という $1$ が何個か連続する整数の ${\rm mod}\ 10^9+7$ の値を最初に全部求めておく．
先頭から $k$ 文字目の数字に関して着目すると，$0 \leq i \leq N-k$ なる $i$ に対して，それが $10^i$ の桁になるパターン数は $k$ パターンある．
これは，その数字が含まれる部分文字列を考えた時，前後それぞれ何文字目までがその部分文字列に含まれるかを考えればわかる．
なので，その数字を $1$ が $N-k+1$ 個続く整数と $k$ を書けて足していけば良い．

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long
#define M 1000000007

int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}return s;}
void writer(int x, char c){int i,sz=0,m=0;char buf[10];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}

char in[210000];
ll pw[210000];

int main(){
  int i, j, k, n;
  ll res = 0;

  pw[0] = 1;
  REP(i,1,210000) pw[i] = pw[i-1] * 10 % M;
  REP(i,1,210000) pw[i] += pw[i-1];

  n = reader(in);
  rep(i,n){
    res += pw[n-1-i] * (in[i]-'0') % M * (i+1) % M;
  }
  res %= M;
  writer((int)res, '\n');

  return 0;
}

Current time: 2024年04月25日16時24分13秒
Last modified: 2014年12月05日03時10分30秒 (by laycrs)
Tags: Competitive_Programming HackerRank HackerRank_w3
トップページに戻る

Logged in as: unknown user (not login)

ログイン：