トップページに戻る
次の競技プログラミングの問題へ
前の競技プログラミングの問題へ
No.129 お年玉(2)
■■■問題■■■
Yasuoは、予算がN円しかないが、親戚の子供M人にお年玉をあげたいと思っている。
お年玉の中に入れる種類は1000円紙幣だけにしたいと思っているが、
なるべく平等でかつ最大の金額をあげたいと思っています。
今回は、前回のように配って予算が余った分も配り「当たり」とすることにした。
準備として、すべてのお年玉袋に、平等で最大な額の1000円紙幣を入れた後に、
予算が余っているなら、「当たり」として、
1つの同じ袋には、1000円をいれるかいれないかとして、
ランダムにそれぞれのお年玉袋に追加で振り分けることにした。
この時、誰がどのお年玉袋がもらえるかはわからないとして、
M人のそれぞれのもらえるお年玉の額の組み合わせは、何通りあるか求めてください。
1000円紙幣にできるなら余りを全て使うものとする。
答えが非常に大きくなるので10の9乗(素数ではないことに注意)で割った余りを求めてください。
■■■入力■■■
N
M
入力は全て整数で与えられる。
1 <= N <= 10の16乗
1 <= M <= 1万
■■■出力■■■
お年玉の額の組み合わせは、何通りあるかを10の9乗で割った余りを求めてください。
最後に改行をしてください。
C#のソース
using System;
using System.Collections.Generic;
class Program
{
static string InputPattern = "Input1";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("10000");
WillReturn.Add("5");
//1
//予算が10000円あり、5人に配るので全員1人あたり平等に2000円です
}
else if (InputPattern == "Input2") {
WillReturn.Add("24500");
WillReturn.Add("9");
//84
//1000円紙幣分を平等に配ると6500円分あまるが、
//残りを1000円紙幣にできるのは6000円分である。
//余った分をランダムに配る。すると84通りの配り方がある。
}
else if (InputPattern == "Input3") {
WillReturn.Add("1000");
WillReturn.Add("6");
//6
//6人のうち誰かが1000円ゲットです
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
Eratosthenes();
List<string> InputList = GetInputList();
ulong N = ulong.Parse(InputList[0]);
int M = int.Parse(InputList[1]);
//余った金額
int RestVal = (int)(N % (1000 * (ulong)M));
Console.WriteLine(DeriveCombiCnt(M, RestVal / 1000));
}
//Aつの袋からBつの袋を選ぶ組み合わせの数を求める
static ulong DeriveCombiCnt(int pA, int pB)
{
if (pA == 0) return 1;
pB = Math.Min(pB, pA - pB);
var ProdList = new List<int>();
var DeviList = new List<int>();
for (int I = pA; I >= pA - pB + 1; I--) {
ProdList.Add(I);
}
for (int I = 1; I <= pB; I++) {
DeviList.AddRange(DeriveSoinsuuArr(I));
}
//分母を全てはらってから、総積を1000000000で割った余りを求める
for (int I = DeviList.Count - 1; 0 <= I; I--) {
for (int J = 0; J <= ProdList.Count - 1; J++) {
if (ProdList[J] % DeviList[I] == 0) {
ProdList[J] /= DeviList[I];
DeviList.RemoveAt(I);
break;
}
}
}
ulong WillReturn = 1;
ProdList.ForEach(X => WillReturn = (WillReturn * (ulong)X) % 1000000000);
return WillReturn;
}
const int Jyougen = 10000;
static int[] SosuuArr;
//エラトステネスの篩
static void Eratosthenes()
{
var CheckArr = new System.Collections.BitArray(Jyougen + 1);
for (int I = 2; I <= CheckArr.Count - 1; I++) {
CheckArr[I] = true;
}
for (int I = 2; I * I <= CheckArr.Count - 1; I++) {
if (I != 2 && I % 2 == 0) continue;
if (CheckArr[I]) {
for (int J = I * 2; J <= CheckArr.Count - 1; J += I) {
CheckArr[J] = false;
}
}
}
var SosuuList = new List<int>();
for (int I = 2; I <= CheckArr.Count - 1; I++)
if (CheckArr[I]) SosuuList.Add(I);
SosuuArr = SosuuList.ToArray();
}
//素因数分解した素因数の配列を返す
static int[] DeriveSoinsuuArr(int pTarget)
{
if (Array.BinarySearch<int>(SosuuArr, pTarget) >= 0) {
return new int[] { pTarget };
}
var SoinsuuList = new List<int>();
for (int I = 0; I <= SosuuArr.GetUpperBound(0); I++) {
while (pTarget % SosuuArr[I] == 0) {
SoinsuuList.Add(SosuuArr[I]);
pTarget /= SosuuArr[I];
}
if (pTarget == 1) break;
}
return SoinsuuList.ToArray();
}
}
解説
袋の数をn、余った金額/1000をrとして、
nCrを求めてます。