网站建设价格最低多少钱,中科 网站会员注册系统建设,做服务的网站吗,广元做网站站排名正题
luogu CF232B 题目大意
给你一个 nmn\times mnm 的网格#xff0c;问你有多少种放点方案可以满足每个 nnn\times nnn 的网格内都恰好有 kkk 个点 解题思路
不难发下#xff0c;nnn\times nnn 的格子往下移一行#xff0c;新的一行和刚过的一行点的数量一样
那么设 …正题
luogu CF232B 题目大意
给你一个 n×mn\times mn×m 的网格问你有多少种放点方案可以满足每个 n×nn\times nn×n 的网格内都恰好有 kkk 个点 解题思路
不难发下n×nn\times nn×n 的格子往下移一行新的一行和刚过的一行点的数量一样
那么设 fi,jf_{i,j}fi,j 表示前 iii 行放了 jjj 个点的方案数然后直接暴力转移即可 code
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 110
#define mod 1000000007
using namespace std;
ll n,m,k,inv[N],fac[N],ifac[N],g[N][N],f[N][N*N];
ll C(ll x,ll y)
{return fac[x]*ifac[x-y]%mod*ifac[y]%mod;
}
ll pw(ll x,ll y)
{ll z1;while(y){if(y1)zz*x%mod;xx*x%mod;y1;}return z;
}
void pre_work()
{ifac[0]fac[0]inv[1]ifac[1]fac[1]1;for(ll i2;in;i){inv[i]mod-mod/i*inv[mod%i]%mod;fac[i]fac[i-1]*i%mod;ifac[i]ifac[i-1]*inv[i]%mod;}for(ll i1;in;i)for(ll j0;jn;j)g[i][j]pw(C(n,j),(m-in)/n);//第i行选j个点的方案数幂为后面一样的行return;
}
int main()
{scanf(%lld%lld%lld,n,m,k);pre_work();f[0][0]1;for(ll i1;in;i)for(ll j0;jk;j)for(ll l0;lmin(j,n);l)(f[i][j]f[i-1][j-l]*g[i][l]%mod)%mod;printf(%lld,f[n][k]);return 0;
}
