牛客国庆集训派对Day4-E-乒乓球(NTT)

2024-01-19 05:59

本文主要是介绍牛客国庆集训派对Day4-E-乒乓球(NTT),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

链接:https://www.nowcoder.com/acm/contest/204/E
来源:牛客网
 

题目描述

小 Bo 是某省乒乓球名列前茅的选手,现在他有 n 颗乒乓球一字排开,第 i 颗乒乓球的权值为 wi
每次他会随机从现有的乒乓球中等概率选一颗拿走,然后得到的收益是这颗球左边第一个乒乓球和右边第一个乒乓球的权值的乘积,如果左边没有乒乓球或者右边没有乒乓球,则收益为 0,这个过程会重复进行到所有球都被拿走为止
现在小 Bo 想知道他的期望总收益
为了方便,你只需要输出答案对 998244353 取模的值

输入描述:

第一行一个正整数 n
第二行 n 个正整数 w1…wn

输出描述:

输出答案对 998244353 取模的值

示例1

输入

复制

3
1 1 1

输出

复制

332748118

说明

答案是 

备注:

1≤ n≤ 105
1≤ wi≤ 107

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long 
#define mod 998244353
ll a[300005],b[300005],n,ans;
ll wn[30];
ll q(ll x,ll y)
{ll res=1;x%=mod;while(y){if(y%2)res=res*x%mod;x=x*x%mod;y/=2;}return res;
}
void getwn()
{for(int i=0;i<20;i++){int  tmp=1<<i;wn[i]=q(3ll,(mod-1)/tmp);}
}
void change(ll y[],int len)
{int i,j,k;for(i=1,j=len/2;i<len-1;i++){if(i<j)            swap(y[i],y[j]);k=len/2;while(j>=k)j-=k,k/=2;if(j<k)j+=k;  }
}
void ntt(ll y[], int len, int on) 
{change(y, len); int id=0;for(int h=2;h<=len;h<<=1){id++;for(int j=0;j<len;j+=h){ll w=1;for(int k=j;k<j+h/2;k++){ll u=y[k];ll t=w*y[k+h/2]%mod;y[k]=(u+t)%mod;y[k+h/2]=(u-t+mod)%mod;w=w*wn[id]%mod;}}}if(on==-1){ll inv=q(len,mod-2);for(int i=1;i<len/2;i++)swap(y[i],y[len-i]);for(int i=0;i<len;i++)y[i]=y[i]*inv%mod;}
}
int main(void)
{getwn();scanf("%lld",&n);for(int i=0;i<n;i++)scanf("%lld",&a[i]);for(int i=0;i<n;i++)b[n-i-1]=a[i];int len=1;while(len<=n*2) len*=2;ntt(a,len,1);ntt(b,len,1);for(int i=0;i<len;i++)a[i]=a[i]*b[i]%mod;ntt(a,len,-1);for(int i=2;i<n;i++)ans=(ans+2ll*a[n+i-1]*q((ll)i*(i+1),mod-2)%mod)%mod;printf("%lld\n",ans);return 0;
}

 

这篇关于牛客国庆集训派对Day4-E-乒乓球(NTT)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/621451

相关文章

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

牛客小白月赛100部分题解

比赛地址:牛客小白月赛100_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ A.ACM中的A题 #include<bits/stdc++.h>using namespace std;#define ll long long#define ull = unsigned long longvoid solve() {ll a,b,c;cin>>a>>b>

牛客小白月赛100(A,B,C,D,E,F三元环计数)

比赛链接 官方讲解 这场比较简单,ABC都很签到,D是个不太裸需要预处理的 B F S BFS BFS 搜索,E是调和级数暴力枚举,F是三元环计数。三元环考的比较少,没见过可能会偏难。 A ACM中的A题 思路: 就是枚举每个边变成原来的两倍,然后看看两短边之和是否大于第三边即可。 不能只给最短边乘 2 2 2,比如 1 4 8 这组数据,也不能只给第二短边乘 2 2 2,比

笔试强训,[NOIP2002普及组]过河卒牛客.游游的水果大礼包牛客.买卖股票的最好时机(二)二叉树非递归前序遍历

目录 [NOIP2002普及组]过河卒 牛客.游游的水果大礼包 牛客.买卖股票的最好时机(二) 二叉树非递归前序遍历 [NOIP2002普及组]过河卒 题里面给的提示很有用,那个马的关系,后面就注意,dp需要作为long的类型。 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publ

2014暑假集训搜索专题

A - 漫步校园 Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Submit Status Description LL最近沉迷于AC不能自拔,每天寝室、机房两点一线。由于长时间坐在电脑边,缺乏运动。他决定充分利用每次从寝室到机房的时间,在校园里散散步。整个HDU校园呈方形布局,可划

每日OJ_牛客_求和(递归深搜)

目录 牛客_求和(递归深搜) 解析代码 牛客_求和(递归深搜) 求和_好未来笔试题_牛客网 解析代码         递归中每次累加一个新的数,如果累加和大于等于目标,结束递归。此时如果累加和正好等于目标,则打印组合。向上回退搜索其它组合。此题本身就是一个搜索的过程,找到所有的组合。 #include <iostream>#include <cmath>#in

中秋国庆请客喝酒,面子与钱包双赢的红酒选择

平时生活中,总少不了各种聚会,不管是朋友小聚,还是正式的商务宴请,酒都是少不了的,而现在,越来越多的人都喜欢选择红酒来助兴。 喝红酒的人不少,懂红酒的人却不多。有时候真的很尴尬,明明环境菜都不错,就是红酒太难喝,每一口都要鼓足勇气才能下咽。 其实,酒也是饭局的重要组成部分,如果酒不好喝,客人事后也是会暗暗吐槽的。所以,一个好的饭局,酒一定也是好的。 这里说的“好”,既要面子上

牛客《剑指Offer》 -- 数值的整数次方

题目描述 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。 思路 特别注意负数的情况,出现负数,将其转化为正数然后求倒数。 class Solution {public:double Power(double base, int exponent) {double total = 1;bool flag = false

牛客网《剑指Offer》 二进制中1的个数

题目描述 输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。 思路 负数用补码,其实就是求一个数据在计算机中是存储是怎么样子的。用位运算,就能很好实现。 class Solution {public:int NumberOf1(int n) {int count = 0;int flag = 1;while (flag != 0) {if ((n & f

牛客网《剑指Offer》 矩形覆盖

题目描述 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法? class Solution {public:int rectCover(int number) {if(number==0) return 0;if(number==1) return 1;if(number==2) return 2;retu