小可爱表白

NC20824. 小可爱表白

描述

$\text{你知道} \mathcal{“Nice\ to\ meet\ you.”} \text{是什么意思吗？}$

$\text{“很高兴遇见你呗”}$
$\text{不啊，有生之年，幸得相逢。}$

小可爱终于鼓起勇气给她喜欢的人表白了，然而，

“对，你就是我最美丽的意外。“

”喜欢你，小可爱~”

没错小可爱把她喜欢的人吓到了

吓的她喜欢的人给她扔了一道数学题并说：“只要你做出来这个，我就跟你在一起”

现在你要帮帮小可爱啦~

题目是这样的：

给定n求

$\sum_{k=1}^n(k * \sum_{j=1}^k \sum_{i=0}^{n-1}(C_{i}^{k-j} * C_{n-i-1}^{j-1}))\ mod\ 998244353$

输入描述

一行一个数n

输出描述

一行一个数表示答案

示例1

输入:

输出:

130959532

上次编辑到这里，代码来自缓存点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 484K, 提交时间: 2018-11-01 20:50:15

#include<bits/stdc++.h>
#define p 998244353
#define int long long
using namespace std;

int n,ans;

inline int mul(int a,int b)
{
	int ans=1;
	for(;b;b>>=1,(a*=a)%=p) if(b&1) (ans*=a)%=p;
	return ans;
}

signed main()
{
	cin>>n;
	cout<<n*(n+1)%p*mul(2,n-2)%p;
}

Python3(3.5.2) 解法, 执行用时: 31ms, 内存消耗: 3328K, 提交时间: 2020-04-17 17:08:11

n=int(input())
k=998244353
print(n*(n+1)%k*pow(2,n-2,k)%k)