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⊆S1≤j≤i≤k)1 \le j \le i \le k)1≤j≤i≤k)排成下面所示边长为kkk的三角形因此总共选出了12k(k1)\frac{1}{2} k(k1)21​k(k1)个子集。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}\cdotsA_{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输入 #12 2输出 #116说明/提示对于100%100\%100%的数据1≤n1 \le n1≤nk≤109k \le 10^9k≤109。C实现#includebits/stdc.husingnamespacestd;longlongbinpow(longlongb,longlongp,longlongk){b%k;longlongres1;while(p0){if(p1)resres*b%k;bb*b%k;p1;}returnres;}intmain(){longlongn,k,Mod1e97;scanf(%lld%lld,n,k);printf(%lld,binpow(2,n*k,Mod));return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容