SRM502 Div2 Hard(1000) TheCowDivTwo

TopCoder

TheCowDivTwo

動的計画法。i番目までの牛からj匹を選んで和をNで割った余りがkとなる組み合わせの個数を覚えておく。

#include <vector>
using namespace std;

class TheCowDivTwo{public:
int find( int N, int K )
{
    int M = 1000000007;

    //  [i][j]　和をNで割った余りがjになるサイズiの部分集合の個数
    vector<vector<long long> > T( K+1, vector<long long>(N) );

    T[0][0] = 1;

    for ( int i=0; i<N; i++ )
    {
        vector<vector<long long> > P = T;

        for ( int j=0; j<=K; j++ )
        for ( int k=0; k<N; k++ )
        {
            T[j][k] = P[j][k];
            if ( j > 0 )
                T[j][k] += P[j-1][(k-i+N)%N];
            T[j][k] %= M;
        }
    }
    
    return (int)T[K][0];
}};