题面

提示：无限输入

题解

一看这题的数据

...............................

这也太大了，必须边输入边取模才行，

但是式子很复杂，所以必须推出一些结论。

因为Xk是有顺序的，所以相当与给班级分名额的经典组合数例子，S(k)就等于C(N-1,K-1)

答案应该是 $\sum_{k = 0}^{n-1}C_{n - 1}^{k}$

这是不是就是杨辉三角的第n行的和？

因为杨辉三角的第n行所有的数都是由顶上的那一个1得到的，每一个数aij对下一行的贡献都是2aij，所以开头的那一个1对第n行的贡献就是 1<<n ，也就是2^(n-1)。

因为1e9 + 7是质数，所以我们用欧拉定理来做： $a^{C}\equiv \left\{\begin{matrix} a^{C\mod\varphi (b)} & (gcd(a,b)=1) & \\ a^{C} & (gcd(a,b)\neq 1 \and C<\varphi(b)) & \\a^{C\mod\varphi(b)+\varphi(b)} & (gcd(a,b)\neq 1 \and C\geq \varphi(b))& \end{matrix}\right.$

CODE

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#define LL long long

using namespace std;

LL mod = 1e9 + 7ll,mod2 = 1e9 + 6ll;

LL n,m,i,j,s,o,k;

char ss[1000005];

LL superread() {

	LL f = 1,x = 0,cn = 0;char s = ss[++cn];

	while(s < '0' || s > '9') {if(s == '-') f = -1;s = ss[++cn];}

	while(s >= '0' && s <= '9') {x = x * 10ll + s - '0';x %= mod2;s = ss[++cn];}

	return x * f % mod2;

}

LL qkpow(LL a,LL b) {

	if(b == 0) return 1;

	if(b == 1) return a;

	LL as = qkpow(a,b >> 1) % mod;

	return as * as % mod * qkpow(a,b & 1) % mod;

}

int main() {

	while(~scanf("%s",ss + 1)) {

		n = superread();

		printf("%lld\n",qkpow(2,n) * qkpow(2,mod - 2) % mod);

	}

	return 0;

}

巴特西

Sum （欧拉定理）

题面

题解

CODE

最新文章

热门文章