记录编号	296679	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]有标号的二分图计数 I	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	1.312 s
提交时间	2016-08-15 20:43:49	内存使用	1.81 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define fac(x) (((x)<(0))?(0):(f[(x)]))
using namespace std;
const int maxn=100010;
const LL p=998244353ll;
LL inv(LL);
LL qpow(LL,LL);
LL C(int,int);
int n;
LL f[maxn<<1],ans=0;
int main(){
#define MINE
#ifdef MINE
	freopen("QAQ_bipartite_one.in","r",stdin);
	freopen("QAQ_bipartite_one.out","w",stdout);
#endif
	scanf("%d",&n);
	f[0]=1ll;
	for(int i=1;i<=n;i++)f[i]=f[i-1]*i%p;
	for(int i=0;i<=n;i++)(ans+=C(n,i)*qpow(2ll,(LL)(n-i)*i%(p-1ll)))%=p;
	printf("%d",(int)ans);
	return 0;
}
LL inv(LL x){
	return qpow(x,p-2ll);
}
LL qpow(LL a,LL b){
	LL ans=1ll;
	for(;b;b>>=1,(a*=a)%=p)if(b&1ll)(ans*=a)%=p;
	return ans;
}
LL C(int n,int m){
	return fac(n)*inv(fac(m)*fac(n-m)%p)%p;
}