Q66 整数倍の得票数

JavaScriptのソース

Solve( 3,  7); //      3
Solve(20,100); //9688804

//N人の候補者に対して、M人が投票する場合の、解を求める
function Solve(pN,pM)
{
    const UB = pM;

    var Answer = 0;
    for(var I = 1 ; I <= UB ; I++){
        if(pM % I == 0 && I * pN <= pM){
            Answer += SolveHelepr(pN,pM,I);
        }
    }
    document.write(pN , '人の候補者に' , pM , '人が投票する場合は、' , Answer , '通り<br>');
}

function SolveHelepr(pN,pM,pMin)
{
    const UB = pM;

    //場合の数[直近の投票数][残りの票数]
    var PrevDP = DeriveDPArr(UB);
    PrevDP[pMin][pM - pMin] = 1;

    //document.write("初期設定<br>");
    //DebugPrint(PrevDP,UB);

    for(var I = 2 ; I <= pN ; I++){
        var CurrDP = DeriveDPArr(UB);

        for(var J = 0 ; J <= UB ; J++){
            for(var K = 0 ; K <= UB ; K++){
                if(PrevDP[J][K] == 0) continue;

                for(var L = 0 ; L <= UB ; L++){ //倍率のループ
                    var NewJ = J + pMin * L;
                    var NewK = K - NewJ;

                    if(NewJ > UB) break;
                    if(NewK < 0) break;
                    CurrDP[NewJ][NewK] += PrevDP[J][K];
                }
            }
        }
        //document.write(I , "でのDP結果<br>");
        //DebugPrint(CurrDP,UB);
        PrevDP = CurrDP;
    }
    
    var WillReturn = 0;
    for(var I = 2 ; I <= UB ; I++){
        if(CurrDP[I][0] > 0)
            WillReturn += CurrDP[I][0];
    }
    return WillReturn;
}

function DeriveDPArr(pUB)
{
    var DPArr = new Array(pUB + 1);
    for(var I = 0 ; I <= pUB ; I++){
        DPArr[I] = new Array(pUB + 1);
        DPArr[I].fill(0);
    }
    return DPArr;
}

//DPのデバッグ用
function DebugPrint(pArr,pUB)
{
    for(var I = 0 ; I <= pUB ; I++){
        for(var J = 0 ; J <= pUB ; J++){
            document.write("pArr[" , I , "][" , J , "]=" , pArr[I][J] , "   ");
        }
        document.write("<br>");
    }
}

実行結果

3人の候補者に7人が投票する場合は、3通り
20人の候補者に100人が投票する場合は、9688804通り

解説

動的計画法で解いてます。