C++のコードがSegmentation faultする。

Question

AtCoderの問題を解くべくC++の次のコードを動かすとSegmentation Faultが出るのですが、原因が分かりません。

#include <bits/stdc++.h>

const long long mo=1000000000+7;

std::string K;
int D;
long long dp[2][50][10001];//1:strict

int main(){
  std::cin>>K;
  std::cin>>D;
  dp[1][0][0]=1;
  for(int i=0;i<(int)(K.length());++i){
    for(int k=0;k<50;++k){
      for(int j=0;j<=9;++j){
        int nk=(j+k)%D;
        dp[0][nk][i+1]+=dp[0][k][i];
        dp[0][nk][i+1]%=mo;
      }
      for(int j=0;j<(int)(K[i]-'0');++j){
        int nk=(j+k)%D;
        dp[0][nk][i+1]+=dp[1][k][i];
        dp[0][nk][i+1]%=mo;
      }
      int nk=(k+(int)(K[i]-'0'))%D;
      dp[1][nk][i+1]+=dp[1][k][i];
      dp[1][nk][i+1]%=mo;
    }
  }
  std::cout<<(dp[0][0][(int)(K.length())]+dp[1][0][(int)(K.length())]-1)%mo<<std::endl;
  return 0;
}

入力は

98765432109876543210
58

です。

gdbでデバッグしてみたのですが、何も情報は得られませんでした。

gdb ./a.out
GNU gdb (GDB) 7.4.1-debian
Copyright (C) 2012 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>...
Reading symbols from a.out...(no debugging symbols found)...done.
(gdb) run
Starting program: a.out
warning: no loadable sections found in added symbol-file system-supplied DSO at 0x7ffff7ffa000
98765432109876543210
58

Program received signal SIGSEGV, Segmentation fault.
0x0000000000400df2 in main ()
(gdb) quit
A debugging session is active.

        Inferior 1 [process 11348] will be killed.

Quit anyway? (y or n) y

原因の分かる方ご教示ください。

Answer 1

入力の58が変数Dに入りますが、これはint nk=(j+k)%D;のように利用されており、このnkはdp[0][nk][i+1]のように利用されています。
しかしlong long dp[2][50][10001];//1:strictによれば49までしか受け付けないので、buffer overrunしていることになります。

検証にはstd::array::at()を利用しました。

https://wandbox.org/permlink/AcVbRe2AxUn7Y7L9

Comments

[yumetodo]

おや、遅かったか。gdbもいいですが、こういうたぐいのはstd::array::at()を使うと追いやすいです。

Answer 2

gdbのメッセージに

Reading symbols from a.out...(no debugging symbols found)...done.

とあります。デバッグシンボルがないので、gdb は情報を出せないのです。
デバッグシンボル付きでコンパイルして下さい。
多分 -g です。

おそらくインデックス(つまり[]の中の数値)がおかしいのだと思います。

Comments

[ruei]

その通りでした！ dp[2][50][10001]をdp[2][100][10001]に変えたらいいということがおかげさまで分かりました。 gdbを使うのは初めてだったので勉強になりました。ありがとうございます。