$P5240 Derivation$

news/2024/4/23 20:39:21/

神仙题。

第一场月赛的题目我到第二场月赛完了才写【由此可见我是真的菜

题目就是个大模拟加乘显然,幂的话需要将原函数、导函数的函数值用扩展欧拉定理展开 \(log\) 层。时间复杂度 \(O(T |S| \log^2p)\)

因为求导时要对指数减一,你可能会用加 (模数-1) 来实现,并且如果你的扩展欧拉定理写法是小于模数时是正常值,超过模数时用真实值 + 模数代替,就会导致错误,因为正常的快速幂中 \(0^0=1\)

\(0^P=0\) \((P≠0)\)

以下不是本人写的程序 是验题人写的

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define MAXN 10005
#define eps 1e-12
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {res = 0;T f = 1;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {res = res * 10 + c - '0';c = getchar();}res *= f;
}
template<class T>
void out(T x) {if(x < 0) {x = -x;putchar('-');}if(x >= 10) {out(x / 10);}putchar('0' + x % 10);
}
const int MOD = 998244353;
char s[MAXN],que[MAXN];
int val[2],tot,phi[MAXN];
vector<pii > sta[2];
bool f[2][MAXN][2];
int eu(int x) {int t = x;for(int i = 2 ; i <= x / i ; ++i) {if(x % i == 0) {t = t / i * (i - 1);while(x % i == 0) x /= i;}}if(x > 1) t = t / x * (x - 1);return t;
}
int fpow(int x,int c,int mod,bool &on) {int64 res = 1,t = x;if(c == 0) {on = 0;return 1;}if(x == 1 || x == 0) return x;while(c && !on) {res = res * x;--c;if(res >= MOD) {res %= mod;on = 1;break;}}while(c) {if(c & 1) res = res * t % mod;t = t * t % mod;c >>= 1;}return res;
}
void Solve() {scanf("%s",s + 2);read(val[0]);read(val[1]);s[1] = '(';int L = strlen(s + 1);s[L + 1] = ')';++L;sta[0].clear();sta[1].clear();tot = 0;int lev = 0;for(int i = 1 ; i <= L ; ++i) {if(s[i] >= '0' && s[i] <= '9') {if(s[i - 1] < '0' || s[i - 1] > '9') {for(int k = 0 ; k <= 1 ; ++k) {int v = s[i] - '0';sta[k].pb(mp(v,(lev == 0 ? 0 : v)));f[k][sta[k].size() - 1][0] = 0;f[k][sta[k].size() - 1][1] = 0;}}else {for(int k = 0 ; k <= 1 ; ++k) {auto t = sta[k].back();int64 a = 1LL * t.fi * 10 + s[i] - '0';int64 b = 1LL * t.se * 10 + s[i] - '0';if(a >= MOD) {f[k][sta[k].size() - 1][0] = 1;a %= phi[lev];}if(b >= MOD) {f[k][sta[k].size() - 1][1] = 1;b %= phi[max(lev - 1,0)];}if(lev == 0) b = 0;t = mp(a,b);sta[k].pop_back();sta[k].push_back(t);}}}else if(s[i] == ')') {if(!tot) break;if(que[tot] == '^') --lev;for(int k = 0 ; k <= 1 ; ++k) {int si = sta[k].size() - 1;auto t0 = sta[k][si - 1],t1 = sta[k][si];sta[k].pop_back();sta[k].pop_back();if(que[tot] == '^') {if(f[k][si][0]) t1.fi += phi[lev + 1];if(f[k][si][1]) t1.se += phi[lev];if(lev) {int a = fpow(t0.fi,t1.fi,phi[lev],f[k][si - 1][0]);int b = fpow(t0.se,t1.se,phi[lev - 1],f[k][si - 1][1]);sta[k].pb(mp(a,b));}else {int a = fpow(t0.fi,t1.fi,MOD,f[k][si - 1][0]);int b = 1LL * t1.se * t0.se % MOD;if(t0.fi != 0)b = 1LL * b * fpow(t0.fi,(1LL * t1.fi + (MOD - 2)) % (MOD - 1),MOD,f[k][si - 1][1]) % MOD;else {if(f[k][si][0]) b = 0;else if(t1.fi - 1) b = 0;}sta[k].pb(mp(a,b));}}else if(que[tot] == '+') {f[k][si - 1][0] |= f[k][si][0];f[k][si - 1][1] |= f[k][si][1];t0.fi = t0.fi + t1.fi;t0.se = t0.se + t1.se;if(t0.fi >= MOD) {t0.fi %= phi[lev];f[k][si - 1][0] |= 1;}if(t0.se >= MOD) {t0.se %= phi[max(0,lev - 1)];f[k][si - 1][1] |= 1;}sta[k].pb(t0);}else if(que[tot] == '*') {if(lev == 0) {int64 a = 1LL * t0.fi * t1.fi % MOD;int64 b = (1LL * t0.fi * t1.se % MOD + 1LL * t1.fi * t0.se % MOD) % MOD;sta[k].pb(mp((int)a,(int)b));}else {if((!f[k][si][0] && t1.fi == 0) || (!f[k][si - 1][0] && t0.fi == 0)) f[k][si - 1][0] = 0;else f[k][si - 1][0] |= f[k][si][0];if((!f[k][si][1] && t1.fi == 0) || (!f[k][si - 1][1] && t0.fi == 0)) f[k][si - 1][1] = 0;else f[k][si - 1][1] |= f[k][si][1];int64 a = 1LL * t0.fi * t1.fi;int64 b = 1LL * t0.se * t1.se;if(a >= MOD) {a %= phi[lev];f[k][si - 1][0] |= 1;}if(b >= MOD) {b %= phi[lev - 1];f[k][si - 1][1] |= 1;}sta[k].pb(mp((int)a,(int)b));}}}--tot;}else if(s[i] == 'x') {sta[0].pb(mp(val[0],1));sta[1].pb(mp(val[1],1));}else {if(s[i] != '(') que[++tot] = s[i];if(s[i] == '^') ++lev;}}out(sta[0][0].se);space;out(sta[1][0].se);enter;
}
int main() {
#ifdef ivorysifreopen("f2.in","r",stdin);
#endifint T;read(T);phi[0] = MOD;for(int i = 1 ; i <= 10000 ; ++i) {phi[i] = eu(phi[i - 1]);}for(int i = 1 ; i <= T ; ++i) {Solve();}
}

转载于:https://www.cnblogs.com/qf-breeze/p/10585627.html


http://www.ppmy.cn/news/554412.html

相关文章

HDU-5240

一个简单的贪心&#xff0c;就是判断是否他有足够时间复习&#xff0c;可以间断的复习。 #include<algorithm> #include<cstdio> #include<cstring> #include<queue> #include<stack> #include<set> #include<map> #include<iost…

HDU5240 Exam

http://acm.hdu.edu.cn/showproblem.php?pid5240 哎 不多说了 比赛的时候被这题折磨的不轻 深刻认识到自己水平还是相当的low&#xff01;&#xff01;&#xff01; 问题&#xff1a;DRD能不能通过全部的考试 前提&#xff1a;如果他能在这个科目考试之前将这个科…

浪潮 NF5240M3 ,NP5540M3 服务器安装2008 R2

1,服务器系统的安装会出现错误的地方一般都是在Raid 卡驱动 略过Raid 卡配置, 具体 http://jingyan.baidu.com/article/ca41422fddfd201eae99ed30.html 安装的过程中,用U盘考入该型号的Raid卡驱动。 把服务器的机器码发给客服,他会给你发一个Raid驱动。放到U盘中加载就O…

浪潮服务器usb安装Linux,[操作系统]浪潮 NF5240M3 服务器安装2008 R2

[操作系统]浪潮 NF5240M3 服务器安装2008 R2 0 2016-07-05 23:00:05 1,服务器系统的安装会出现错误的地方一般都是在Raid 卡驱动 略过Raid 卡配置, 具体 http://jingyan.baidu.com/article/ca41422fddfd201eae99ed30.html 2.准备好2008R2 系统光盘 以下所举例的是由"用安…

hdu5240

想了辣么多 貌似就一个条件 #include<bits/stdc.h> using namespace std; int flag0;int main(){int t,n,kase1;scanf("%d",&t);while(t--){flag0;scanf("%d",&n);for(int i0;i<n;i){int r,e,l;scanf("%d%d%d",&r,&e,&…

Leetcode 5240:串联字符串的最大长度

题目描述 给定一个字符串数组 arr&#xff0c;字符串 s 是将 arr 某一子序列字符串连接所得的字符串&#xff0c;如果 s 中的每一个字符都只出现过一次&#xff0c;那么它就是一个可行解。 请返回所有可行解 s 中最长长度。 示例 1&#xff1a; 输入&#xff1a;arr ["…

NetBackup5240一体机奶妈级教程3.2升级到3.3.0.2

更新前备份Catlog&#xff08;全备&#xff09;关闭所有job及policy 安装检查包&#xff1a; NetBackup Appliance Upgrade Readiness Analyzer 对于3.2版本&#xff0c;请安装SYMC_NBAPP_update_ReadinessAnalyzer-8.0.3-1.noarch.rpm 检查条目显示[WARNING]的可以忽略.看不到…

NBU5240备份系统还原数据库---Windows版

NBU5240是一个基于系统文件和多种数据库备份的灾备系统&#xff0c;灵活性比较高。下面具体记录如何利用该系统的备份文件进行数据库还原。&#xff08;基于业务场景&#xff09; 公司某业务部门突然发现前台系统数据有异常&#xff0c;已经是几天前的跑出来的数据了&#xff0…

【算法】代码随想录、数组——长度最小的子数组、滑动窗口实现

209.长度最小的子数组 解法思想来自代码随想录&#xff1a;209.长度最小的子数组 &#xff08;1&#xff09;暴力解法 我们暴力解法直接使用两个for循环&#xff0c;然后不断的遍历寻找符合条件的子序列&#xff1b; 初始化长度变量length和结果变量result为0和int类型最大数…

VMware Fusion安装VMware Tools

文章目录 1.安装VMware Tools2.配置共享文件夹 1.安装VMware Tools 下载 需要在系统内部安装&#xff0c;不启动系统无法安装。 移动到桌面&#xff08;下载完成后会在这里显示&#xff09;&#xff0c;将安装包复制到可安装的位置 解压、安装 tar -zxvf VMware Tools-10.3…

Win10安装VMware15.5

一、下载VMware 下载地址&#xff1a;https://www.vmware.com/cn/products/workstation-pro/workstation-pro-evaluation.html&#xff0c;选择Workstation 15.5 Pro for Windows 二、安装VMware 1.双击安装包&#xff0c;弹出安装向导对话框&#xff0c;单击“下一步” 2.…

VMware16安装Win10系统图文教程

VMware16安装Win10系统图文教程 一、 VMware16以及Win10 iso镜像文件准备二、VMware16创建虚拟机三、安装Win10操作系统 一、 VMware16以及Win10 iso镜像文件准备 1.VMware16下载链接:VMwaer16-选择Windows. 2.Win10 iso镜像文件下载:msdn-操作系统-windows 10-第一个. 二、…

Win7安装VMware

Win7安装VMware 下载Vmware 下载链接&#xff1a;https://download.csdn.net/download/weixin_44021888/86948258?spm1001.2014.3001.5503 安装步骤 2.1 双击启动安装程序 2.2 下一步 2.3 下一步&#xff0c;可修改安装路径 2.4 下一步 2.5 下一步 2.6 安装 2.7 安装成…

VMware10出现VMware Workstation 不可恢复错误: (vmx)

在我的VMware10中安装了Ubuntu12&#xff0c; 昨晚还正常关机的呢&#xff0c;今天早上一打开&#xff0c;竟然报错了&#xff0c;错误如图&#xff1a; 上网搜索了下&#xff0c;没有找到比较合适的方法&#xff0c;最后&#xff0c;我在没有卸载VMware的情况下&#xff0c;重…

VMware10中安装Centos网络无法使用的处理办法

Centos7 32位 找不到网卡&#xff0c;网络连接不可用 原因&#xff1a;Vmware无法识别网卡&#xff0c;导致虚拟机无法上网 处理&#xff1a;由于Vmware虚拟网卡和linux兼容问题导致驱动无法正常安装&#xff0c;默认的网卡类型不兼容 找到Vmware虚拟机文件夹&#xff0c;将V…

彻底删除VMware虚拟机

您是否和我一样被VMware气到了呢&#xff0c;您是否再也不想理VMware了呢&#xff0c;您是否不想再在自己电脑上看到VMware这几个英文字母了呢&#xff0c;来吧&#xff0c;跟着我的步骤&#xff0c;一起和VMware说拜拜吧~~~ 一. 在卸载VMware虚拟机之前&#xff0c;要先把与VM…

VMwareWorkstation下载链接

Github版&#xff1a;https://github.cdnweb.icu/201853910/VMwareWorkstation/blob/master/README.md 文章目录 最新版本直链VMwareWorkstation 17VMwareWorkstation 16VMwareWorkstation 15VMwareWorkstation 14VMwareWorkstation 12VMwareWorkstation 11VMwareWorkstation 1…

VMware虚拟机安装Win10教程

VMware虚拟机安装Win10教程 1.打开VMware Workstation软件&#xff0c;点击创建新的虚拟机 2.选择好要安装的镜像文件&#xff0c;点击打开 3.点击浏览更换虚拟机位置 4.这里建议的磁盘大小为60G&#xff0c;可以根据自己的实际需要更改磁盘大小 5.点击自定义硬件&#x…

win10安装VMware PowerCLI

第一种方法、PowerCLI在线安装 我的电脑始终安装不成功&#xff0c;可能是国内墙的原因&#xff0c;推荐第二种方法 窗口键S 打开搜索&#xff0c;输入 PowerShell # 输入命令 Install-Module -Name VMware.PowerCLI -Scope CurrentUser如果您希望它可供计算机的所有用户使…

在linux中安装vmware,如何在linux中安装VMWare虚拟机

这篇文章主要为大家详细介绍了无桌面的linux安装VMWare Tools配置教程&#xff0c;具有一定的参考价值&#xff0c;感兴趣的小伙伴们可以参考一下 本文为大家分享了linux安装VMWare Tools配置教程&#xff0c;供大家参考&#xff0c;具体内容如下 1、在vmware虚拟机选项下&…