SRM572 Div2 Hard "DistinctRemainders"
問題
以下のような特徴を持った
整数の配列S = (S[1], S[2], ..., S[K])を考える。
- K >= 1.
- S[i](1 <= i <= K) で S[i]は0以上の整数である。
- S[1] + S[2] + S[3] ... +S[K-1] + S[K] が N となる。
- S[1] mod M, S[2] mod M ... S[K] mod M が 全部違う値になる。
NとMが与えられた時、上記の特徴を満たす配列が何パターンできるかを返せ。
2つの配列S1,S2において、S1[i] != S2[i]となるiが1つでもあれば、
それは違うパターンとなる。
制約
1 <= N <= 10^18
1 <= M <= 50
解き方
例として、N = 20 M = 7で考えてみる。
同じmodを使っちゃダメなんだから、配列Sの要素数は7以下となるはず。
何個か配列を作ってみると・・・
- 4 + 16....(modの合計=6)
mod | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 | |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
- 5 + 15....(modの合計=6)
mod | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 | |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
- 2 + 8 + 10....(modの合計=6)
mod | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 | |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
- 2 + 7 + 11....(modの合計=6)
mod | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 | |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
- 3 + 4 + 13....(modの合計=13)
mod | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 | |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
合計をNにするように、配列を作るには、
その配列のmodの合計sumが、
N % M == sum % Mとなればいいんじゃないかなとなる。
mod2と4の二個を使った配列は
(2 + 18), (9 + 11), (4 + 16)が作れる
mod | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 | |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
mod1と5の二個を使った配列は
(1 + 19), (8 + 12), (5 + 15)が作れる
mod | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 | |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
という感じで、modの使う種類数(2と4,1と5で2種類)と、その合計値(6)が同じなら、
数値の組み合わせの数(3)は同じになるんじゃないかなとなる。
じゃあ組み合わせの数はどうやって出せばいいかというと
例えばmodの種類を3, 合計値を6 mod 1, 2, 3で配列を作る場合
すべてのmodで最小値(level 0)を選び、その合計値をNから引くと、
Nまでどのぐらい足りないかが分かる。
mod | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
Lv0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
Lv1 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
Lv2 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
この場合だと20 - 6 = 14
また、この合計値はmodの合計値と同じである
この足りない分をMで割ると、levelをどれだけ上げればNになるかが分かる。
14 / 7 = 2(level)
つまり、3つのmod達に、2つのlevelを振り分けてあげればよい。
- mod1にlevel2つ振り分ける。
mod | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
Lv0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
Lv1 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
Lv2 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
- mod1とmod2に1つずつ振り分ける。
mod | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
Lv0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
Lv1 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
Lv2 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
これは重複組み合わせとなり、
modの種類をn、振り分けるlevelをm とすると、
数の組み合わせはnHm = m+n-1Cn-1となる。
あとは、n=3 m=2になるようなのが何個あるだとか、階乗を掛けたりすればおk
事後
自分も良く分かってない部分もあるので、
この解き方は考え方が間違ってる部分があるかも・・
ソースコードはchokudaiさんのとかカンニング。
getC()の部分で何故powmod()を使うと上手くいくのかが分かってない。
nCmの乗数と除数の割り切れるようなペアを見つけて
一回乗数を割っちゃってから掛け算していく方法をとってる人もいた。
ソースコード
typedef long long ll; const int MAX_M = 50; const int MAX_SUM = (MAX_M - 1) * MAX_M / 2; const int MOD = 1000000007; int dp[MAX_M+1][MAX_SUM+1]; class DistinctRemainders { public: // (a^b) % MODを返す ll powmod( ll a, ll b ){ if( b == 0 ) return 1; if( b % 2 == 0 ){ ll r = powmod( a, b / 2 ); return (r * r) % MOD; }else{ ll r = powmod( a, b - 1 ); return (r * a) % MOD; } } // nCmを返す ll getC( ll n, ll m ){ if( n < 0 ) return 0; if( n < m ) return 0; ll r = 1; ll d = 1; for( int i = 0; i < m; i++ ){ r *= (n - i) % MOD; r %= MOD; d *= i + 1; d %= MOD; } return (r * powmod( d, MOD - 2 )) % MOD; // 謎・・・なぜMOD-2?? } int howMany(long long N, int M){ const int max_sum = (M - 1) * M / 2; // mod合計値の最大 // dpを初期化 // dp[i][j] = i種類のmodを使って合計jの組み合わせが何通りできるか for( int i = 0; i <= MAX_M; i++ ){ for( int j = 0; j <= MAX_SUM; j++ ){ dp[i][j] = 0; } } dp[0][0] = 1; for( int i = 0; i < M; i++ ){ for( int j = i; j >= 0; j-- ){ for( int k = 0; k <= max_sum; k++ ){ dp[j+1][k+i] += dp[j][k]; dp[j+1][k+i] %= MOD; } } } // 階乗 ll kaijo[MAX_M+1]; kaijo[0] = 1; for( int i = 0; i < M; i++ ){ kaijo[i+1] = (kaijo[i] * (i+1)) % MOD; } // 数え上げてく ll ret = 0; for( int sum = N % M; sum <= max_sum; sum += M ){ for( int num = 1; num <= M; num++ ){ ll add = dp[num][sum]; ll m = (N - sum) / M; // 配るmodレベル ll n = num; // mod戦士たちの数 add *= getC( m + n - 1, n - 1 ); // nHm = m+n-1Cn-1 重複組み合わせ add %= MOD; add *= kaijo[num]; // 階乗を掛ける add %= MOD; ret += add; ret %= MOD; } } return static_cast<int>(ret); } };