Codeforces Round #144(Div. 1), problem: (B) Table DP 조합 수학

1303 단어
제목: 네모난 칸을 가득 채운 행렬에 검은 점을 놓는 방안 수를 구하십시오. 행렬에 있는 n*n의 하위 행렬의 검은 점은 모두 k입니다.
방법: 매 열의 A[i]에 놓인 검은 점수가 A[i+n]과 같다는 것을 추측해 보면 DP가 될 수 있다. 대신의 문제가 있으면 나는 더 이상 말하지 않겠다.
#include <cstdio>
#include <iostream>
#define mod 1000000007
#define LL long long
const int LMT=102;
using namespace std;
LL c[LMT][LMT],dp[LMT][10004],val[LMT][2];
void init(void)
{
    for(int i=0;i<LMT;i++)c[i][0]=c[i][i]=1;
    for(int i=1;i<LMT;i++)
      for(int j=1;j<i;j++)
      {
          c[i][j]=c[i-1][j-1]+c[i-1][j];
          c[i][j]%=mod;
      }
}
LL mypow(LL x,LL y)
{
    LL ret=1;
    while(y)
    {
        if(y&1)ret*=x;
        ret%=mod;
        x*=x;
        x%=mod;
        y>>=1;
    }
    return ret;
}
int main(void)
{
    int n,k;
    init();
    LL p,m;
    scanf("%d%I64d%d",&n,&m,&k);
    dp[0][0]=1;
    for(int i=0;i<=n;i++)
    {
        val[i][0]=mypow(c[n][i],m/n);
        val[i][1]=(val[i][0]*c[n][i])%mod;
    }
    for(int i=1;i<=n;i++)
    {
     for(int j=0;j<=k;j++)
       for(int t=j;t>=0&&j-t<=n;t--)
       {
           p=(m%n>=i);
           dp[i][j]+=dp[i-1][t]*val[j-t][p];
           dp[i][j]%=mod;
       }
    }
       cout<<dp[n][k]<<endl;
    return 0;
}

좋은 웹페이지 즐겨찾기