打卡信奥刷题（2986）用C++实现信奥题 P6075 [JSOI2015] 子集选取

P6075 [JSOI2015] 子集选取

题目描述

给定nnn个元素的集合S={1,2,⋯ ,n}S= \left\{1,2,\cdots,n \right\}S={1,2,⋯,n}和整数 $ k$，现在要从SSS中选出若干子集Ai,j (A⊆SA_{i,j}\ (A \subseteq SAi,j​(A⊆S，1≤j≤i≤k)1 \le j \le i \le k)1≤j≤i≤k)排成下面所示边长为kkk的三角形（因此总共选出了12k(k+1)\frac{1}{2} k(k+1)21​k(k+1)个子集）。
A1,1A2,1A2,2A3,1A3,2A3,3⋮⋮⋮⋱Ak,1Ak,2Ak,3⋯Ak,k\begin{matrix} A_{1,1}\\ A_{2,1}&A_{2,2}\\ A_{3,1}&A_{3,2}&A_{3,3}\\ \vdots&\vdots&\vdots&\ddots\\ A_{k,1}&A_{k,2}&A_{k,3}&\cdots&A_{k,k} \end{matrix}A1,1​A2,1​A3,1​⋮Ak,1​​A2,2​A3,2​⋮Ak,2​​A3,3​⋮Ak,3​​⋱⋯​Ak,k​​

此外，JYY 对选出的子集之间还有额外的要求：选出的这些子集必须满足
Ai,j⊆Ai,j−1A_{i,j} \subseteq A_{i,j-1}Ai,j​⊆Ai,j−1​且Ai,j⊆Ai−1,jA_{i,j} \subseteq A_{i-1,j}Ai,j​⊆Ai−1,j​。
JYY 想知道，求有多少种不同的选取这些子集的方法。因为答案很大，JYY 只关心输出答案模1,000,000,0071{,}000{,}000{,}0071,000,000,007的值。

对于两种选取方案A={A1,1,A2,1,⋯ ,Ak,k}A = \left\{ A_{1,1} , A_{2,1} ,\cdots, A_{k,k} \right\}A={A1,1​,A2,1​,⋯,Ak,k​}和B={B1,1,B2,1,⋯ ,Bk,k}B = \left\{ B_{1,1} , B_{2,1} ,\cdots, B_{k,k} \right\}B={B1,1​,B2,1​,⋯,Bk,k​}只要存在i,ji,ji,j满足Ai,j≠Bi,jA_{i,j} \neq B_{i,j}Ai,j​=Bi,j​，我们就认为AAA和BBB是不同的方案。

输入格式

输入包含一行两个整数nnn和kkk。

输出格式

一行一个整数，表示不同方案数目模1,000,000,0071,000,000,0071,000,000,007的值。

输入输出样例 #1

输入 #1

2 2

输出 #1

16

说明/提示

对于100%100\%100%的数据，1≤n1 \le n1≤n，k≤109k \le 10^9k≤109。

C++实现

#include<bits/stdc++.h>usingnamespacestd;longlongbinpow(longlongb,longlongp,longlongk){b%=k;longlongres=1;while(p>0){if(p&1)res=res*b%k;b=b*b%k;p>>=1;}returnres;}intmain(){longlongn,k,Mod=1e9+7;scanf("%lld%lld",&n,&k);printf("%lld",binpow(2,n*k,Mod));return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容