Description
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiI0NXYFhGd192UvwVe0lmdhJ3ZvwFM38CXlZHbvN3cpR2Lc1TPB10QGtWUCpEMJ9CXsxWam9CXwADNvwVZ6l2c052bm9CXUJDT1wkNhVzLcRnbvZ2Lc1zaq1kZkpHWrxGSiZXUYpVd1kmYr50MZV3YyI2cKJDT29GRjBjUIF2LcRHelR3LcJzLctmch1mclRXY39zMxAjMwIzMwITMxIDM3EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
Analysis
设 F(n,k) 表示读入n,k的答案
First step
考虑到每个元素之间其实是互相独立的,所以 F(n,k)=F(1,k)n
我们只需快速求出 F(1,k)
Second step
这是一个三角形
A[i] 表示第i列最后一个1的行(该行以上全为1,以下全为0)
显然有 A[i]>=A[i+1]
设 G[i][j] 表示第i行,最后一个1的行为j的方案数,则
G[i][j]=∑kp=jG[i−1][p]=G[i−1][j]+G[i][j+1]
这便是组合数的形式
写出来,发现其实是倒放的杨辉三角
G[i,j]
1
14
136
1234
11111
因为可以在任意一个位置结束,也可以全不选,所以
F(1,k)=1+∑G[i][j]=2k
所以 Ans=2nk
Code
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=,mo=+;
ll n,k;
ll qmi(ll x,ll n)
{
ll t=;
for(;n;n>>=)
{
if(n&) t=t*x%mo;
x=x*x%mo;
}
return t;
}
int main()
{
freopen("subset.in","r",stdin);
freopen("subset.out","w",stdout);
scanf("%lld %lld",&n,&k);
printf("%lld\n",qmi(,n*k));
return ;
}