HackerRank Ad Infinitum - Math Programming Contest May'14 4問目 - Manasa and Sub-sequences

Source

HackerRank Ad Infinitum - Math Programming Contest May'14 4問目
problem statement（コンテストページ）
problem statement

問題概要

数字のみからなる長さ $N$ の文字列 $S$ が与えられる．
各部分列について，数字をつなげて $10$ 進数の整数とみなしたとき，各部分列が表す整数の和は幾つになるかを ${\rm mod}\ 1000000007\ (10^9+7)$ で求める問題．
部分列として最初が $0$ であるものも考える．

解法

入力として，最初の $k$ 文字のみが与えられた場合の答えを $R_k$ として，漸化式を作る．
その際，部分列の数 $2^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];

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

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

  return 0;
}

Current time: 2024年04月19日01時11分17秒
Last modified: 2014年09月23日00時00分30秒 (by laycrs)
Tags: Competitive_Programming HackerRank HackerRank_infinitum-may14
トップページに戻る

Logged in as: unknown user (not login)

ログイン：