淮安建设工程协会网站查询,郑州做软件开发的公司,响应式大学网站,展厅平面设计文章目录T1#xff1a;分数转换题目题解代码实现T2#xff1a;Slow Path Finding Algorithm题目题解代码实现T3#xff1a;切面包题目题解代码实现T1#xff1a;分数转换
题目
Time limit: 1.5 seconds Memory limit: 512 megabytes
给定一个十进制小数#xff0c;请你…
文章目录T1分数转换题目题解代码实现T2Slow Path Finding Algorithm题目题解代码实现T3切面包题目题解代码实现T1分数转换
题目
Time limit: 1.5 seconds Memory limit: 512 megabytes
给定一个十进制小数请你将它转换为分数。 给定的小数可能有循环节用 [] 表示如 0.12[3] 表示 0.1233333…
Input 输入文件包含多组测试数据。 第一行一个整数 T (1 ≤ T ≤ 3 · 105 )表示测试数据的组数。 每组测试数据一行一个字符串 s i 表示需要转换的小数保证 1 ≤ |s i | ≤ 18且保证由符号部分整数 部分、小数点、小数部分组成整数部分没有前导零如果小数部分有循环节则循环节一定在末尾且 循环节的最后一位非零。 Output 每组测试数据输出一行一个分数 p/q其中 p, q 为整数且 q ≥ 1, gcd(p,q) 1
Scoring 本题共有 3 个测试点 测试点 1 (30 分)保证给定小数没有循环节 测试点 2 (30 分)保证给定小数的整数部分为 0且循环节是整个小数部分 测试点 3 (40 分)无特殊限制
Example frac.in 5 -0.0 0.[3] 1926.0[817] 1.00 -123.456 frac.out 0/1 1/3 19241557/9990 1/1 -15432/125
题解
旁边的dalao都说这是一道小学奥数题。。。 而我则是在考场上用尽了计算机看了多少数据才发现了规律
简略题解如下 对于测试点 1直接写成 p/10k 后约分即可 对于测试点 2假设循环节为 t长度为 k则可以列出方程 10kx x t解出来即可 对于测试点 3只需在测试点 2 的基础上多一些细节处理 接下来就让大家一起来找规律吧 可以多打几组表看看会发现规律如下 循环节其实就是分子舍掉前导零而循环节的个数就对应分母的9的个数 这个规律发现后整道题就变成了一个水题 1.首先对于没有循环节的输入如 123.1025 大家肯定都知道将其转化为1231025/100001231025/100001231025/10000然后在用gcd去约分化到最简即可不再过多赘述 2.只有整数和循环节的输入如 123.[7851] 就先把循环小数通过上面的规律化成分数7851/99997851/99997851/9999在把整数与之同分再化简也是gcd去完成 .3.整数小数循环节都有的输入如样例 1926.0[817] 就先把整数与小数进行合并同分再化简这样就又转换成了情况2同样的处理即可
也就是说先把输入处理成(19260[817])/10(19260[817])/10(19260[817])/10再变成了(19260817999)/10(19260\frac{817}{999})/10(19260999817)/10 变成192681799901926\frac{817}{9990}19269990817再同分化简就ok了 代码里有一些细节处理这里就不再一一解释大家可以自行看懂。。。 代码实现
#include cmath
#include cstdio
#include cstring
#include iostream
using namespace std;
#define LL long long
#define MAXN 20
int T;
char s[MAXN];LL gcd ( LL x, LL y ) {if ( ! y )return x;return gcd ( y, x % y );
}int main() {scanf ( %d, T );while ( T -- ) {scanf ( %s, s );int len strlen ( s );bool flag1 0, flag2 0;int digit 0;LL cnt1 0, cnt2 0, cnt3 0;LL tot1 0, tot2 0, tot3 0;while ( digit len s[digit] - ) {flag1 1;digit ;}while ( digit len s[digit] ! . ) {cnt1 ( cnt1 3 ) ( cnt1 1 ) ( s[digit] - 0 );digit ; tot1 ;}if ( s[digit] . )digit ;while ( digit len s[digit] ! [ ) {cnt2 ( cnt2 3 ) ( cnt2 1 ) ( s[digit] - 0 );digit ;tot2 ;}if ( s[digit] [ ) {digit ;flag2 1;}while ( digit len s[digit] ! ] ) {cnt3 ( cnt3 3 ) ( cnt3 1 ) ( s[digit] - 0 );digit ;tot3 ;}LL N ( LL ) pow ( 10, tot2 );LL d, fenzi, fenmu;if ( tot2 ! 0 ) {d gcd ( cnt1 * N cnt2, N );fenzi ( cnt1 * N cnt2 ) / d;fenmu N / d;}else {fenzi N;if ( cnt1 0 )fenzi 0;fenmu 1;}if ( cnt1 0 cnt2 0 cnt3 0 )flag1 0;if ( flag1 )printf ( - );if ( ! flag2 ) {printf ( %lld/%lld\n, fenzi, fenmu );continue;}N ( LL ) ( pow ( 10, tot3 ) ) - 1;N N * ( LL ) ( pow ( 10, tot2 ) ); d gcd ( cnt3, N );LL newfenzi cnt3 / d;LL newfenmu N / d;if ( newfenmu fenmu ) {d gcd ( fenzi newfenzi, fenmu );printf ( %lld/%lld\n, ( fenzi newfenzi ) / d, fenmu / d );}else {d gcd ( newfenmu, fenmu );LL lcm newfenmu * ( fenmu / d );fenzi fenzi * ( lcm / fenmu );newfenzi newfenzi * ( lcm / newfenmu );d gcd ( newfenzi fenzi, lcm );printf ( %lld/%lld\n, ( fenzi newfenzi ) / d, lcm / d );}}return 0;
}T2Slow Path Finding Algorithm
题目
Time limit: 6 seconds Memory limit: 512 megabytes
小 H 今天学习了「缓慢的路径寻找算法」 下课后便准备找一道题练习一下。题目是这样的给定一张 有向图每条边上都有一个小写英文字母小 H 需要寻找一条路径使得路径上出现最多的字母的出现次 数最大。然而小 H 想了很久也只会 |V | 1 的情形于是他找到了你请你帮他解决这个问题
Input 输入文件包含多组测试数据。 第一行一个整数 T (1 ≤ T ≤ 105 )表示测试数据的组数。 每组测试数据的第一行两个整数 n, m (1 ≤ n ≤ 105 , 0 ≤ m ≤ 2 · 105 )分别表示有向图的点数和边数 接下来 m 行每行两个整数 u i , v i (1 ≤ u i ,v i ≤ n) 和一个小写英文字母 c i 表示从 u i 到 v i 有一条有向 边上面的字母为 c i 。 保证 ∑n ≤ 10 6 ,∑m ≤ 2 · 10 6 。 Output 对于每组测试数据如果路径上出现最多的字母的出现次数可以是任意大输出一行 -1 否则在第一行依次输出一个整数 ans一个字母 c 和一个整数 k (1 ≤ k ≤ n)依次表示路径上出现最 多的字母的出现次数达到最多出现次数的字母以及路径上的点数 第二行输出 k 个整数 p 1 ,p 2 ,…,p k (1 ≤ p i ≤ n)表示这条路径依次经过的点 如果有多条满足条件的路径输出任意一条
Scoring 本题共有 5 个测试点每个测试点 20 分。 测试点 1n,m ≤ 5。 测试点 2每组测试数据中的 c i 均相同。 测试点 3T,n,m ≤ 100。 测试点 4保证图中不存在环。 测试点 5无特殊限制。
Example spfa.in 3 1 0 1 1 1 1 a 4 6 1 2 i 1 3 a 1 4 k 2 3 i 2 4 o 3 4 i spfa.out 0 a 1 1 -1 3 i 4 1 2 3 4
Note 在第一组数据中只有一个点没有边所以唯一的路径就是 [1]其中每个字母的出现次数都是 0。 在第二组数据中有一个点和它到自己的一条边只需要选择路径 [1,1,1,…]就能使得字母 a 出现任 意多次
题解
首先我们能知道如何判断-1的情况如果一个字母能出现任意多次证明有一条路可以一直重复走这一条边那么图中肯定是有环的所以我们可以用拓扑排序找环 处理了-1的情况后再来思考对于这种树上路径求极值很容易就想到DPDPDP 设DP[i][j]DP[i][j]DP[i][j]表示走到i号点为止字母j出现的最多次数
而这里我们采取用父亲更新儿子节点的值原因如下 1.我们不知道真正的起点到底是谁只能知道目前的终点为i 2.如果用父亲更新儿子就可以在拓扑排序找环的时候就一起处理了
所以状态转移方程式如下v是u的一个儿子节点c是这条边上的字母 DP[v][j]max(DP[v][j],DP[u][j](cj))DP[v][j]max(DP[v][j],DP[u][j](cj))DP[v][j]max(DP[v][j],DP[u][j](cj)) 最后就是路径输出问题了其实可以在DP的时候顺便把DP[v][j]DP[v][j]DP[v][j]状态下取最大值时所指向的父亲节点记录一下就可以了
这里在找的时候顺序会从终点找到起点所以我们可以用stack栈来后进先出把路径倒着输出 也可以vector存储后用一个翻转函数reverse输出也可以
代码实现
#include queue
#include stack
#include cstdio
#include vector
#include iostream
using namespace std;
#define MAXN 100005
queue int q;
stack int path;
vector vector pair int, int G ( MAXN );
int T, n, m;
int d[MAXN];
int dp[MAXN][30], f[MAXN][30];int main() {scanf ( %d, T );while ( T -- ) {scanf ( %d %d, n, m );for ( int i 1;i n;i ) {G[i].clear();d[i] 0;for ( int j 0;j 26;j )dp[i][j] f[i][j] 0;}for ( int i 1;i m;i ) {int u, v;char c;scanf ( %d %d %c, u, v, c );G[u].push_back( make_pair ( v, c - a ) );d[v] ;}int tot 0;for ( int i 1;i n;i )if ( ! d[i] ) {q.push ( i );tot ;}while ( ! q.empty() ) {int t q.front();q.pop();for ( int i 0;i G[t].size();i ) {int v G[t][i].first;int c G[t][i].second;for ( int j 0;j 26;j )if ( dp[t][j] ( c j ) dp[v][j] ) {dp[v][j] dp[t][j] ( c j );f[v][j] t;}d[v] --;if ( ! d[v] ) {q.push ( v );tot ;}}}if ( tot ! n )printf ( -1\n );else {int result -1, str, idx;for ( int i 1;i n;i )for ( int j 0;j 26;j )if ( dp[i][j] result ) {result dp[i][j];str j;idx i;}while ( idx ! 0 ) {path.push ( idx );idx f[idx][str];}printf ( %d %c %d\n, result, str a, path.size() );while ( ! path.empty() ) {printf ( %d , path.top() );path.pop();}printf ( \n );}}return 0;
}它终于来了
T3切面包
题目
Time limit: 1 second Memory limit: 512 megabytes 小 H 有条一长长的面包。这条面包由 n 段组成。 每当有朋友到小 H 的家里玩小 H 就会切下这块面包的一段分享给朋友们。之后小 H 又会重新制 作和之前完全一样的若干段面包填充切下的部分。 面包被切下时有可能会裂开第 i 段面包被切下时裂开的概率为pi998244352\frac{pi}{998244352}998244352pi 。小 H 想让朋友尽可能开 心于是会把裂开的面包自己吃掉而用没有裂开的面包招待朋友。小 H 特别喜欢分块因此如果小 H 有 x 段连续的没有裂开的面包则朋友的开心度为 x2 有时小 H 也会对一段面包进行加工加工会改变面包裂开的概率 你需要在每次小 H 切蛋糕之前回答他朋友的期望开心度是多少
Input 第一行两个整数 n, m (1 ≤ n,m ≤ 105)分别表示面包的长度和时间的次数。 第二行 n 个整数 p 1 ,p 2 ,…,p n (0 ≤ pi ≤ 998244352)表示每段面包初始时裂开的概率。 接下来 m 行每行表示一个事件 1 x i q i (1 ≤ x i ≤ n, 0 ≤ q i ≤ 998244352)——表示小 H 加工了第 x i 段面包加工后 p[x i] 变成了 q i 2 l i r i (1 ≤ l i ≤ r i ≤ n)——表示小 H 询问若切下 [l i ,r i ] 内的面包朋友的期望开心度是多少 Output 对每个 2 事件输出一个整数表示朋友的期望开心度对 998244353 取模后的值
Scoring 本题共有 5 个测试点每个测试点 20 分 测试点 11 ≤ n,m ≤ 20 测试点 2p i 499122176没有 1 事件 测试点 3没有 1 事件 测试点 41 ≤ n,m ≤ 2 · 103 测试点 5无特殊限制
Example divide.in 3 5 499122176 499122176 499122176 2 1 1 2 1 2 2 1 3 1 2 0 2 1 3 divide.out 499122177 249561089 748683266 1
Note
题解
简略题解如下 对于测试点 1直接枚举所有情况。时间复杂度 O(n m2n) 对于测试点 2答案只和长度有关可以发现答案其实是长度的一个二次函数直接计算即可 也可以通过递推求出。时间复杂度 O(n m) 接下来我们需要进行一定的推导。引入辅助变量 xi当第 i 段裂开时 xi 1否则 xi 0。 连续段的数量可以看作初始的一段加上断开的连接处再减去删去的段数即 1∑i1n−1(xixi1−xixi1)−∑i1nxi1∑i2n−1xi−∑i1n−1xixi11\sum_{i1}^{n-1}(x_ix_{i1}-x_ix_{i1})-\sum_{i1}^nx_i1\sum_{i2}^{n-1}x_i-\sum_{i1}^{n-1}x_ix_{i1}1i1∑n−1(xixi1−xixi1)−i1∑nxi1i2∑n−1xi−i1∑n−1xixi1 则段数的平方为 1∑2≤in∑2≤jnxixj∑1≤in∑1≤jnxixi1xjxj12∑2≤inxi−2∑1≤inxixi1−2∑2≤in∑1≤jnxixjxj11\sum_{2≤in}\sum_{2≤jn}x_ix_j\sum_{1≤in}\sum_{1≤jn}x_ix_{i1}x_jx_{j1}2\sum_{2≤in}x_i-2\sum_{1≤in}x_ix_{i1}-2\sum_{2≤in}\sum_{1≤jn}x_ix_jx_{j1}12≤in∑2≤jn∑xixj1≤in∑1≤jn∑xixi1xjxj122≤in∑xi−21≤in∑xixi1−22≤in∑1≤jn∑xixjxj1 将上式用pip_ipi表示得到 1(∑i2n−1pi)23∑i2n−1pi−∑i2n−1pi2(∑i1n−1pipi1)22∑i1n−2pipi1pi2−2∑i2n−2pipi12pi21(\sum_{i2}^{n-1}p_i)^23\sum_{i2}^{n-1}p_i-\sum_{i2}^{n-1}p_i^2(\sum_{i1}^{n-1}p_ip_{i1})^22\sum_{i1}^{n-2}p_ip_{i1}p_{i2}-2\sum_{i2}^{n-2}p_ip_{i1}^2p_{i2}1(i2∑n−1pi)23i2∑n−1pi−i2∑n−1pi2(i1∑n−1pipi1)22i1∑n−2pipi1pi2−2i2∑n−2pipi12pi2 −5∑i1n−1pipi12∑i2n−1pi2pi12∑i1n−2pipi12−∑i1n−1pi2pi12−2(∑i2n−1pi)(∑i1n−1pipi1)2p1p22pn−1pn-5\sum_{i1}^{n-1}p_ip_{i1}2\sum_{i2}^{n-1}p_i^2p_{i1}2\sum_{i1}^{n-2}p_ip_{i1}^2-\sum_{i1}^{n-1}p_i^2p_{i1}^2-2(\sum_{i2}^{n-1}p_i)(\sum_{i1}^{n-1}p_ip_{i1})2p_1p_2 2p_{n-1}p_n−5i1∑n−1pipi12i2∑n−1pi2pi12i1∑n−2pipi12−i1∑n−1pi2pi12−2(i2∑n−1pi)(i1∑n−1pipi1)2p1p22pn−1pn 对于测试点 3直接记录前缀和即可。时间复杂度 O(n m) 对于测试点 4暴力查询。时间复杂度 O(nm) 对于测试点 5使用数据结构维护 pi,pi2,pipi1,pi2pi1,pipi12,pi2pi12,pipi1pi2,pipi12pi2p_i, p_i^2, p_ip_{i1}, p_i^2p_{i1}, p_ip_{i1}^2, p_i^2p_{i1}^2, p_ip_{i1}p_{i2}, p_ip_{i1}^2p_{i2}pi,pi2,pipi1,pi2pi1,pipi12,pi2pi12,pipi1pi2,pipi12pi2的和即可,时间复杂度 O(n m lg n)。 接下来进入本蒟蒻的自己尽力详解版我会尽自己的全力把这个递推式推导给大家看的 1∑i1n−1(xixi1−xixi1)−∑i1nxi1∑i2n−1xi−∑i1n−1xixi11\sum_{i1}^{n-1}(x_ix_{i1}-x_ix_{i1})-\sum_{i1}^nx_i1\sum_{i2}^{n-1}x_i-\sum_{i1}^{n-1}x_ix_{i1}1i1∑n−1(xixi1−xixi1)−i1∑nxi1i2∑n−1xi−i1∑n−1xixi1 首先对于这个等式其实我们直接推右边来得更快 这个就是我们假设每个碎掉的面包把面包分成了多段每两个碎掉的面包彼此之间不冲突 意思就是i面包没有和i1面包一起碎掉因为这样的话其实只相当于一段长度为i面包和i1面包长度之和的面包把左右分成了两段并非我们理想的如上图一样分成3段i与i1面包之前没有完整的面包 这就是1∑i2n−1xi1\sum_{i2}^{n-1}x_i1∑i2n−1xi部分
然而这只是我们的理想状态真正是可能多个碎的面包碎在一起形成一个更长的碎面包这个时候分的段数就少了1和n的端点也可能是碎的这就是−∑i1n−1xixi1-\sum_{i1}^{n-1}x_ix_{i1}−∑i1n−1xixi1为什么只有两个呢 想一想我们把i和i1合并成了一个大的碎面包如果i2面包也碎了就再与它合并相当于两两合并 关于以上公式的平方展开式相信大家都会我就不再赘述进入最难环节我们一项一项地看这个展开式是如何一步一步合并成下面那一大堆东西的
这里用pip_ipi带换了xix_ixi用事件代换01这就导致出现了下面的公式 首先要明白两个概念 pi∗pipip_i*p_ip_ipi∗pipi 表示的意义pi事件和pi事件同时发生的概率就是pi事件发生的概率 pipj≠pi∗pjp_ip_j≠p_i*p_jpipjpi∗pj 表示的意义pi事件发生的概率和pj事件发生的概率并不等于pi和pj事件同时发生的概率 ①1就不变直接往下移好了我们已经处理好了16\frac{1}{6}61 ② ∑2≤in∑2≤jnxixj\sum_{2≤in}\sum_{2≤jn}x_ix_j2≤in∑2≤jn∑xixj 这个如果代换成了事件p那么这里面就一种情况是错误的即pi∗pipip_i*p_ip_ipi∗pipi就不满足上述公式 我们得先把错误的概率减掉再加上真的概率也就转化成了 (∑i2n−1pi)2−∑i2n−1pi2∑i2n−1pi(\sum_{i2}^{n-1}p_i)^2-\sum_{i2}^{n-1}p_i^2\sum_{i2}^{n-1}p_i(i2∑n−1pi)2−i2∑n−1pi2i2∑n−1pi ③ ∑2≤in∑1≤jnxixi1xjxj1\sum_{2≤in}\sum_{1≤jn}x_ix_{i1}x_jx_{j1}2≤in∑1≤jn∑xixi1xjxj1 与②同样的思想这里面算错了ij,ij1,ji1ij,ij1,ji1ij,ij1,ji1三种情况在这里要明白ij1,ji1ij1,ji1ij1,ji1本质上是一致的因为i和j只是我们的一个循环变量名罢了我们换一下也是不会影响的所以下面的j我就都写成了i
对于ijijij的情况就得减去多算的pipi1p_ip_{i1}pipi1对于ij1,ji1ij1,ji1ij1,ji1的情况得减去多算的pi1p_{i1}pi1情况,我们就先把错误算的所有概率都减掉再把这种情况时的正确概率加上 因为有两种前面的系数就是2也就转化成了 (∑i1n−1pipi1)22∑i1n−2pipi1pi2−2∑i1n−2pipi12pi2−∑i1n−1pi2pi12∑i1n−1pipi1(\sum_{i1}^{n-1}p_ip_{i1})^22\sum_{i1}^{n-2}p_ip_{i1}p_{i2}-2\sum_{i1}^{n-2}p_ip_{i1}^2p_{i2}-\sum_{i1}^{n-1}p_i^2p_{i1}^2\sum_{i1}^{n-1}p_ip_{i1}(i1∑n−1pipi1)22i1∑n−2pipi1pi2−2i1∑n−2pipi12pi2−i1∑n−1pi2pi12i1∑n−1pipi1 ④2∑2≤inxi2\sum_{2≤in}x_i22≤in∑xi 对于这种情况舒服吧不用变通直接转移成 2∑i2n−1pi2\sum_{i2}^{n-1}p_i2i2∑n−1pi ⑤−2∑1≤inxixi1-2\sum_{1≤in}x_ix_{i1}−21≤in∑xixi1 对于这种情况也是不会有冲突的可以直接转移 −2∑i1n−1pipi1-2\sum_{i1}^{n-1}p_ip_{i1}−2i1∑n−1pipi1 ⑥−2∑2≤in∑1≤jnxixjxj1-2\sum_{2≤in}\sum_{1≤jn}x_ix_jx_{j1}−22≤in∑1≤jn∑xixjxj1 这里冲突的情况就是ij,ij1ij,ij1ij,ij1先减掉错误的概率统计再加上正确的 由于这个式子前面的符号是−-−我们就变成加回统计错误的部分再减掉正确的 −2(∑i2n−1pi)(∑i1n−1pipi1)−4∑i1n−1pipi12∑i1n−1pi2pi12∑i1n−1pipi12-2(\sum_{i2}^{n-1}p_i)(\sum_{i1}^{n-1}p_ip_{i1})-4\sum_{i1}^{n-1}p_ip_{i1}2\sum_{i1}^{n-1}p_i^2p_{i1}2\sum_{i1}^{n-1}p_ip_{i1}^2−2(i2∑n−1pi)(i1∑n−1pipi1)−4i1∑n−1pipi12i1∑n−1pi2pi12i1∑n−1pipi12 注意观察与下列式子区别在哪里 −2(∑i2n−1pi)(∑i1n−1pipi1)−4∑i1n−1pipi12∑i2n−1pi2pi12∑i1n−2pipi12-2(\sum_{i2}^{n-1}p_i)(\sum_{i1}^{n-1}p_ip_{i1})-4\sum_{i1}^{n-1}p_ip_{i1}2\sum_{i2}^{n-1}p_i^2p_{i1}2\sum_{i1}^{n-2}p_ip_{i1}^2−2(i2∑n−1pi)(i1∑n−1pipi1)−4i1∑n−1pipi12i2∑n−1pi2pi12i1∑n−2pipi12 区别1 2∑i1n−1pi2pi1,2∑i2n−1pi2pi12\sum_{i1}^{n-1}p_i^2p_{i1},2\sum_{i2}^{n-1}p_i^2p_{i1}2i1∑n−1pi2pi1,2i2∑n−1pi2pi1 发现少了一次i1i1i1的值累加那我们把它加回来 2∑i1n−1pi2pi12∑i2n−1pi2pi12p1p22\sum_{i1}^{n-1}p_i^2p_{i1}2\sum_{i2}^{n-1}p_i^2p_{i1}2p_1p_22i1∑n−1pi2pi12i2∑n−1pi2pi12p1p2 区别2 2∑i1n−1pipi12,2∑i1n−2pipi122\sum_{i1}^{n-1}p_ip_{i1}^2,2\sum_{i1}^{n-2}p_ip_{i1}^22i1∑n−1pipi12,2i1∑n−2pipi12 发现少了一次in−1in-1in−1的值累加那我们也把它加回来 2∑i1n−1pipi122∑i1n−2pipi122pn−1pn2\sum_{i1}^{n-1}p_ip_{i1}^22\sum_{i1}^{n-2}p_ip_{i1}^22p_{n-1}p_n2i1∑n−1pipi122i1∑n−2pipi122pn−1pn 最后我们把这种情况转移成 −2(∑i2n−1pi)(∑i1n−1pipi1)−4∑i1n−1pipi12∑i2n−1pi2pi12∑i1n−2pipi122p1p22pn−1pn-2(\sum_{i2}^{n-1}p_i)(\sum_{i1}^{n-1}p_ip_{i1})-4\sum_{i1}^{n-1}p_ip_{i1}2\sum_{i2}^{n-1}p_i^2p_{i1}2\sum_{i1}^{n-2}p_ip_{i1}^22p_1p_22p_{n-1}p_n−2(i2∑n−1pi)(i1∑n−1pipi1)−4i1∑n−1pipi12i2∑n−1pi2pi12i1∑n−2pipi122p1p22pn−1pn 这也就是为什么我们用p代替x的时候公式里面出现了常数项的原因 最后把这拆开的六个式子合并同类项得到了上述公市
出于对代码更好操作的数据结构维护和便于合并我们才把最后一种情况拆了一下 接下来就是如何维护八个不同的p求和实话告诉你就是八棵线段树 但我选择了重载一次加号一棵线段树维护八个不同的值。。。
代码实现
#include cstdio
#define mod 998244353
#define LL long long
#define MAXN 100005
struct node {LL p, p2, pp, p2p, pp2, p2p2, ppp, pp2p;node ( LL p 0, LL p2 0, LL pp 0, LL p2p 0, LL pp2 0, LL p2p2 0, LL ppp 0, LL pp2p 0 ) :p ( p ), p2 ( p2 ), pp ( pp ), p2p ( p2p ), pp2 ( pp2 ), p2p2 ( p2p2 ), ppp ( ppp ), pp2p ( pp2p ) {}
}tree[MAXN 2];
int n, m;
LL p[MAXN];node operator ( const node u, node v ) {return node ( ( u.p v.p ) % mod, ( u.p2 v.p2 ) % mod, ( u.pp v.pp ) % mod, ( u.p2p v.p2p ) % mod,( u.pp2 v.pp2 ) % mod, ( u.p2p2 v.p2p2 ) % mod,( u.ppp v.ppp ) % mod, ( u.pp2p v.pp2p ) % mod );
}void count ( int num, int i ) {tree[num].p p[i] % mod;tree[num].p2 p[i] * p[i] % mod;tree[num].pp p[i] * p[i 1] % mod;tree[num].p2p tree[num].p2 * p[i 1] % mod;tree[num].pp2 tree[num].pp * p[i 1] % mod;tree[num].ppp tree[num].pp * p[i 2] % mod;tree[num].pp2p tree[num].pp2 * p[i 2] % mod;tree[num].p2p2 tree[num].pp * tree[num].pp % mod;
}void build ( int num, int l, int r ) {if ( l r ) {count ( num, l );return;}int mid ( l r ) 1;build ( num 1, l, mid );build ( num 1 | 1, mid 1, r );tree[num] tree[num 1] tree[num 1 | 1];
}void update ( int num, int l, int r, int id ) {if ( l r ) {count ( num, id );return;}int mid ( l r ) 1;if ( id mid )update ( num 1, l, mid, id );elseupdate ( num 1 | 1, mid 1, r, id );tree[num] tree[num 1] tree[num 1 | 1];
}node range_sum ( int num, int l, int r, int L, int R ) {if ( L l r R )return tree[num];int mid ( l r ) 1;node lsum( 0, 0, 0, 0, 0, 0, 0, 0 ), rsum( 0, 0, 0, 0, 0, 0, 0, 0 );if ( L mid )lsum range_sum ( num 1, l, mid, L, R );if ( mid R )rsum range_sum ( num 1 | 1, mid 1, r, L, R );return lsum rsum;
}LL query ( int l, int r ) {if ( l r )return ( 1 - p[l] mod ) % mod;node t range_sum ( 1, 1, n, l, r );t.p ( ( t.p - p[r] - p[l] ) % mod mod ) % mod;t.p2 ( ( t.p2 - p[r] * p[r] % mod - p[l] * p[l] % mod ) % mod mod ) % mod;t.p2p ( ( t.p2p - p[l] * p[l] % mod * p[l 1] % mod- p[r] * p[r] % mod * p[r 1] % mod ) % mod mod ) % mod;t.pp2 ( ( t.pp2 - p[r - 1] * p[r] % mod * p[r] % mod- p[r] * p[r 1] % mod * p[r 1] % mod ) % mod mod ) % mod;t.pp ( ( t.pp - p[r] * p[r 1] % mod ) % mod mod ) % mod;t.p2p2 ( ( t.p2p2 - p[r] * p[r] % mod * p[r 1] % mod * p[r 1] % mod ) % mod mod ) % mod;t.ppp ( ( t.ppp - p[r - 1] * p[r] % mod * p[r 1] % mod- p[r] * p[r 1] % mod * p[r 2] % mod ) % mod mod ) % mod;t.pp2p ( ( t.pp2p - p[r - 1] * p[r] % mod * p[r] % mod * p[r 1] % mod- p[r] * p[r 1] % mod * p[r 1] % mod * p[r 2] % mod ) % mod mod ) % mod;LL ans ( ( 1 t.p * t.p % mod 3 * t.p % mod - t.p2 t.pp * t.pp % mod 2 * t.ppp % mod - 2 * t.pp2p % mod - 5 * t.pp % mod 2 * t.p2p % mod 2 * t.pp2 % mod - t.p2p2 - 2 * t.p * t.pp % mod 2 * p[l] * p[l 1] % mod 2 * p[r - 1] * p[r] % mod ) % mod mod ) % mod;return ans;
}int main() {scanf ( %d %d, n, m );for ( int i 1;i n;i ) {scanf ( %lld, p[i] );p[i] ( mod - p[i] ) % mod; }build ( 1, 1, n );for ( int i 1;i m;i ) {int opt;scanf ( %d, opt ); if ( opt 1 ) {int x, q;scanf ( %d %d, x, q );p[x] ( mod - q ) % mod;update( 1, 1, n, x );if ( x 1 )update ( 1, 1, n, x - 1 );if ( x 2 )update ( 1, 1, n, x - 2 );}else {int l, r;scanf ( %d %d, l, r );printf ( %lld\n, query ( l, r ) % mod );}} return 0;
}如果对于推导过程有疑惑的看不明白的可以随时评论也欢迎指出打错的部分太多了错打了几个字符很正常谢谢
