質問編集履歴
5
打消し
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -7,9 +7,9 @@
|
|
|
7
7
|
n = 26033 までは正常に動作するのですが、n が26034以上になると急にプログラムが正常に動作しなくなります。具体的には出力まで達することなくプログラムが終了するようになります。
|
|
8
8
|
|
|
9
9
|
(8/27追記)
|
|
10
|
-
皆様ご回答ありがとうございます。お返事が遅くなってしまい大変申し訳ありません。皆様のアドバイスをもとにループを使う方式と、末尾再帰を用いる方式の2パターンで試してみました。末尾再帰を用いる方式ではn が100万を超えるような大きさの問題でも途中で止まることなく計算ができるようです。一方でループを用いる方式では、n が20万程度のところでループがストップしてしまうようです。どちらにせよ今回はn が10万以下の想定なので問題はありませんが、後学のためにこのような差異が表れた原因についてお教えいただけますと幸いです。
|
|
10
|
+
皆様ご回答ありがとうございます。お返事が遅くなってしまい大変申し訳ありません。皆様のアドバイスをもとにループを使う方式と、末尾再帰を用いる方式の2パターンで試してみました。~~末尾再帰を用いる方式ではn が100万を超えるような大きさの問題でも途中で止まることなく計算ができるようです。一方でループを用いる方式では、n が20万程度のところでループがストップしてしまうようです。どちらにせよ今回はn が10万以下の想定なので問題はありませんが、後学のためにこのような差異が表れた原因についてお教えいただけますと幸いです。~~
|
|
11
11
|
|
|
12
|
-
最初に作成した末尾再帰のコードは配列に階乗の値を格納することができなかったため、配列に値を格納できるよう末尾再帰を書き直しました。しかしこのコードもまたn が10万強のところでストップしてしまうようです。
|
|
12
|
+
~~最初に作成した末尾再帰のコードは配列に階乗の値を格納することができなかったため、配列に値を格納できるよう末尾再帰を書き直しました。しかしこのコードもまたn が10万強のところでストップしてしまうようです。~~
|
|
13
13
|
|
|
14
14
|
大変初歩的なミスでお恥ずかしい限りなのですが、回答者様からご指摘をいただき MAX_N を書き換えていなかったことが原因と分かりました。そのために配列へのアクセスのある関数は途中で止まってしまったようです。MAX_N をもっと大きな値で書き換えた場合、MAX_N 以下の n では末尾再帰、ループともに正常に動作することを確認いたしました。
|
|
15
15
|
|
4
問題の解決
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -11,6 +11,8 @@
|
|
|
11
11
|
|
|
12
12
|
最初に作成した末尾再帰のコードは配列に階乗の値を格納することができなかったため、配列に値を格納できるよう末尾再帰を書き直しました。しかしこのコードもまたn が10万強のところでストップしてしまうようです。
|
|
13
13
|
|
|
14
|
+
大変初歩的なミスでお恥ずかしい限りなのですが、回答者様からご指摘をいただき MAX_N を書き換えていなかったことが原因と分かりました。そのために配列へのアクセスのある関数は途中で止まってしまったようです。MAX_N をもっと大きな値で書き換えた場合、MAX_N 以下の n では末尾再帰、ループともに正常に動作することを確認いたしました。
|
|
15
|
+
|
|
14
16
|
### 該当のソースコード
|
|
15
17
|
|
|
16
18
|
```C++
|
3
コードの追記
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -9,6 +9,8 @@
|
|
|
9
9
|
(8/27追記)
|
|
10
10
|
皆様ご回答ありがとうございます。お返事が遅くなってしまい大変申し訳ありません。皆様のアドバイスをもとにループを使う方式と、末尾再帰を用いる方式の2パターンで試してみました。末尾再帰を用いる方式ではn が100万を超えるような大きさの問題でも途中で止まることなく計算ができるようです。一方でループを用いる方式では、n が20万程度のところでループがストップしてしまうようです。どちらにせよ今回はn が10万以下の想定なので問題はありませんが、後学のためにこのような差異が表れた原因についてお教えいただけますと幸いです。
|
|
11
11
|
|
|
12
|
+
最初に作成した末尾再帰のコードは配列に階乗の値を格納することができなかったため、配列に値を格納できるよう末尾再帰を書き直しました。しかしこのコードもまたn が10万強のところでストップしてしまうようです。
|
|
13
|
+
|
|
12
14
|
### 該当のソースコード
|
|
13
15
|
|
|
14
16
|
```C++
|
|
@@ -87,6 +89,30 @@
|
|
|
87
89
|
}
|
|
88
90
|
```
|
|
89
91
|
|
|
92
|
+
末尾再帰＋配列格納(modFactor(n, 0, 1) を呼ぶとn! までの階乗とその逆元が全て求まるようにしました)
|
|
93
|
+
```C++
|
|
94
|
+
long long modFactor(long long n, long long i, long long f)
|
|
95
|
+
{
|
|
96
|
+
modfac[i] = f;
|
|
97
|
+
if (n == i) {
|
|
98
|
+
modfacinv[n] = modPow(modfac[n], MOD - 2);
|
|
99
|
+
modFactorInv(n, modfacinv[n]);
|
|
100
|
+
return f;
|
|
101
|
+
}
|
|
102
|
+
return modFactor(n, i + 1, ((i + 1) * f) % MOD);
|
|
103
|
+
}
|
|
104
|
+
|
|
105
|
+
long long modFactorInv(long long i, long long f)
|
|
106
|
+
{
|
|
107
|
+
if (i == 0) {
|
|
108
|
+
modfacinv[i] = f;
|
|
109
|
+
return f;
|
|
110
|
+
}
|
|
111
|
+
modfacinv[i] = f;
|
|
112
|
+
return modFactorInv(i - 1, (i * f) % MOD);
|
|
113
|
+
}
|
|
114
|
+
```
|
|
115
|
+
|
|
90
116
|
ループを用いる方式((M - 1)! の逆元がM(M!)^-1 で求められることを用いています)
|
|
91
117
|
```C++
|
|
92
118
|
// n!を求める
|
2
コードの追記
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -6,6 +6,9 @@
|
|
|
6
6
|
|
|
7
7
|
n = 26033 までは正常に動作するのですが、n が26034以上になると急にプログラムが正常に動作しなくなります。具体的には出力まで達することなくプログラムが終了するようになります。
|
|
8
8
|
|
|
9
|
+
(8/27追記)
|
|
10
|
+
皆様ご回答ありがとうございます。お返事が遅くなってしまい大変申し訳ありません。皆様のアドバイスをもとにループを使う方式と、末尾再帰を用いる方式の2パターンで試してみました。末尾再帰を用いる方式ではn が100万を超えるような大きさの問題でも途中で止まることなく計算ができるようです。一方でループを用いる方式では、n が20万程度のところでループがストップしてしまうようです。どちらにせよ今回はn が10万以下の想定なので問題はありませんが、後学のためにこのような差異が表れた原因についてお教えいただけますと幸いです。
|
|
11
|
+
|
|
9
12
|
### 該当のソースコード
|
|
10
13
|
|
|
11
14
|
```C++
|
|
@@ -69,4 +72,45 @@
|
|
|
69
72
|
```
|
|
70
73
|
|
|
71
74
|
### 試したこと
|
|
72
|
-
関数 modfactor の中の modfacinv[n] = (modPow(n, MOD - 2) * modfacinv[n - 1]) % MOD; の記述を消したところ n = 65139 まで正常に計算できるようになりました。このプログラムでは modfacinv は使っていませんが、元々コンビネーションの計算用に作っていたプログラムなのでこちらも計算できるようにしたいと思っています。
|
|
75
|
+
関数 modfactor の中の modfacinv[n] = (modPow(n, MOD - 2) * modfacinv[n - 1]) % MOD; の記述を消したところ n = 65139 まで正常に計算できるようになりました。このプログラムでは modfacinv は使っていませんが、元々コンビネーションの計算用に作っていたプログラムなのでこちらも計算できるようにしたいと思っています。
|
|
76
|
+
|
|
77
|
+
|
|
78
|
+
###(8/27追記)
|
|
79
|
+
末尾再帰を用いる方式
|
|
80
|
+
```C++
|
|
81
|
+
long long modfactor(long long n, long long f)
|
|
82
|
+
{
|
|
83
|
+
if (n == 1) {
|
|
84
|
+
return f;
|
|
85
|
+
}
|
|
86
|
+
return modfactor(n - 1, (n * f) % MOD);
|
|
87
|
+
}
|
|
88
|
+
```
|
|
89
|
+
|
|
90
|
+
ループを用いる方式((M - 1)! の逆元がM(M!)^-1 で求められることを用いています)
|
|
91
|
+
```C++
|
|
92
|
+
// n!を求める
|
|
93
|
+
long long modfactor(long long n)
|
|
94
|
+
{
|
|
95
|
+
modfac[0] = 1;
|
|
96
|
+
long long p = 1;
|
|
97
|
+
while (p <= n) {
|
|
98
|
+
//cout << p << "\n";
|
|
99
|
+
modfac[p] = (p * modfac[p - 1]) % MOD;
|
|
100
|
+
p++;
|
|
101
|
+
}
|
|
102
|
+
modfacinv[n] = modPow(modfac[n], MOD - 2);
|
|
103
|
+
modfactorInv(n);
|
|
104
|
+
return modfac[n];
|
|
105
|
+
}
|
|
106
|
+
|
|
107
|
+
// (n!)^-1 を求める
|
|
108
|
+
void modfactorInv(long long n)
|
|
109
|
+
{
|
|
110
|
+
long long p = n - 1;
|
|
111
|
+
while (p >= 0) {
|
|
112
|
+
modfacinv[p] = ((p + 1) * modfacinv[p + 1]) % MOD;
|
|
113
|
+
p--;
|
|
114
|
+
}
|
|
115
|
+
}
|
|
116
|
+
```
|
1
コード内のコメントの修正
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -1,6 +1,6 @@
|
|
|
1
1
|
### 前提・実現したいこと
|
|
2
2
|
|
|
3
|
-
nを入力として受け取り、n! を 1000000007（10^9 + 7）で
|
|
3
|
+
nを入力として受け取り、n! を 1000000007（10^9 + 7）で割った余りを表示するプログラムを作ろうとしています。nの大きさとしては10万以下を想定しているのですが、nが数万程度以上になると急にプログラムが正常に動作しなくなるという問題が発生しています。原因を突き止めて正常に動作させたいと思っています。
|
|
4
4
|
|
|
5
5
|
### 発生している問題・エラーメッセージ
|
|
6
6
|
|
|
@@ -25,7 +25,7 @@
|
|
|
25
25
|
long long modfacinv[MAX_N + 1];
|
|
26
26
|
|
|
27
27
|
long long modPow(long long x, long long a);
|
|
28
|
-
long long modfactor(long long
|
|
28
|
+
long long modfactor(long long n);
|
|
29
29
|
|
|
30
30
|
int main()
|
|
31
31
|
{
|
|
@@ -40,7 +40,7 @@
|
|
|
40
40
|
return 0;
|
|
41
41
|
}
|
|
42
42
|
|
|
43
|
-
// x^a をMODで割った
|
|
43
|
+
// x^a をMODで割った余りを求める
|
|
44
44
|
long long modPow(long long x, long long a)
|
|
45
45
|
{
|
|
46
46
|
if (a == 1)
|
|
@@ -54,7 +54,7 @@
|
|
|
54
54
|
}
|
|
55
55
|
|
|
56
56
|
|
|
57
|
-
// n!を求める
|
|
57
|
+
// n! をMODで割った余りを求める
|
|
58
58
|
long long modfactor(long long n)
|
|
59
59
|
{
|
|
60
60
|
if (n == 0) {
|