題目鏈接： http://www.acdream.net/problem.php?id=1014
題意：n個(gè)篩子，每個(gè)篩子m個(gè)面（標(biāo)有數(shù)字1到m）。n個(gè)篩子前K大的篩子數(shù)字之和為p的有多少種？
思路：f[i][j][k][t]表示i分成j個(gè)數(shù)的和，j個(gè)數(shù)中最大的數(shù)為k，最小的數(shù)為t。計(jì)算的時(shí)候，枚舉最大和最小的數(shù)字，再枚舉在K個(gè)中最小數(shù)字出現(xiàn)的次數(shù)以及n-K個(gè)中最小數(shù)字出現(xiàn)的次數(shù)。
?
#include <iostream>
#include <stdio.h>
#define i64 long long
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
using namespace std;
i64 f[245][25][15][15],C[25][25];
void init()
{
int i,j,k,p,d;
for(i=1;i<=12;i++) f[i][1][i][i]=1;
for(j=1;j<=20;j++) for(i=0;i<=240;i++) for(k=0;k<=12;k++)
{
for(p=0;p<=k;p++) if(f[i][j][k][p]) for(d=1;d<=12&&i+d<=240;d++)
{
f[i+d][j+1][max(k,d)][min(p,d)]+=f[i][j][k][p];
}
}
for(i=1;i<=20;i++)
{
C[i][0]=C[i][i]=1;
for(j=1;j<i;j++) C[i][j]=C[i-1][j]+C[i-1][j-1];
}
}
int n,m,K,p;
i64 POW(i64 a,i64 b)
{
i64 ans=1;
while(b)
{
if(b&1) ans=ans*a;
a=a*a;
b>>=1;
}
return ans;
}
int main()
{
init();
while(scanf("%d%d%d%d",&n,&m,&K,&p)!=-1)
{
if(p>K*m)
{
puts("0");
continue;
}
i64 ans=0,i,j,k,t,cnt1,cnt2;
for(i=1;i<=m;i++) for(j=1;j<=i&&j*K<=p;j++)
{
for(cnt1=1;cnt1*j<=p&&cnt1<=K;cnt1++) for(cnt2=0;cnt2<=n-K;cnt2++)
{
k=0;
if(cnt1*j==p)
{
if(i==j) k=1;
else continue;
}
else
{
for(t=j+1;t<=i;t++) k+=f[p-cnt1*j][K-cnt1][i][t];
}
ans+=k*C[n][K-cnt1]*C[n-(K-cnt1)][cnt1+cnt2]*POW(j-1,n-K-cnt2);
}
}
printf("%lld\n",ans);
}
return 0;
}
?
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫(xiě)作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
