【模拟赛】纪中提高A组 19.8.4 测试
Task.1 锻造
题目大意：现在勇者想要锻造一把 \(n\) 级的武器。每把武器有两个属性值 \(b,c\)。若想把一把 \(x\) 级武器锻造到 \(x+1\) 级，那么就需要一把 \(y\ (y=\max(x-1,0))\) 级的武器，两把武器成功融合成一把 \(x+1\) 级武器的概率是 \(\frac{min(c_x,b_y)}{c_x}\)，失败两把武器则会融合成 \(\max(x-1,0)\) 级。初始可以花费 \(a\) 个金币直接获得一把 \(0\) 级剑（不限量）。求获得 \(n\) 级武器的期望花费。
数据范围：\(0\leq N,a\leq 10^7,0\leq b_x,b_y,c_x,c_y<p<10^7\)
首先在思考这个锻造出 \(1\) 级剑的情况是怎么样的：买了两把 \(0\) 级剑，\(\frac{min(c_0,b_0)}{c_0}\) 的概率成功（\(2a\)）；\(1-\frac{min(c_0,b_0)}{c_0}\)的概率失败，获得一把 \(0\) 级剑，再买一把，\(\frac{min(c_0,b_0)}{c_0}\times(1-\frac{min(c_0,b_0)}{c_0})\) 的概率成功（\(3a\)）；\((1-\frac{min(c_0,b_0)}{c_0})^2\)的概率失败，获得一把 \(0\) 剑...
有没有发现，这个问题就像算抛硬币第一次抛出正面的期望。如果像上面那样无穷无尽的算下去，很难有结果。
我们先去思考抛硬币的这个问题，答案会是 \(\sum^{+\infin}_{i=1}\frac{1}{2^i}\times i\)，这个东西等于 \(2\)。（级数求和...）
对于一个事件发生的概率为 \(p\)，那么这件事情第一次发生的概率为 \(\frac{1}{p}\) 。
回到这道题。获得一把 \(0\) 级剑的期望显然是 \(a\) 。
\(1\) 级剑需要至少一把 \(0\) 级剑和若干把 \(0\) 级剑。因为失败了只会少一把剑，再买一把就可以了，那么买 \(期望\) 把就能得到获得 \(1\) 级剑的期望花费。
对于之后的 \(i\) 级的剑，需要一把 \(i-1\) 级剑和一把 \(i-2\) 级剑，失败后 \(i-2\) 级剑不会消失，所以我们只需要在失败之后再搞一把 \(i-1\) 级剑。
整理一下上述思路，我们得到了这样的转移方程：
\[
\begin{cases}
f[0]=a\\
f[1]=f[i-1]*(\frac{c_{i-1}}{min(c_{i-1},b_{\max(i-2,0)})})+f[\max(i-2,0)]
\end{cases}
\]
复杂度 \(O(N)\)。
\(Source:\) JZOJ 6271 锻造
代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#pragma GCC optimize(2)
using namespace std;
template<class T>void read(T &x){
x=0; char c=getchar();
while(c<'0'||'9'<c)c=getchar();
while('0'<=c&&c<='9'){x=(x<<1)+(x<<3)+(c^48); c=getchar();}
}
const int N=10000050;
const int mod=998244353;
int n,a;
int bx,by,cx,cy,p;
int b[N],c[N];
int inv[N],f[N];
int main(){
// freopen("forging.in","r",stdin);
// freopen("forging.out","w",stdout);
scanf("%d%d%d%d%d%d%d",&n,&a,&bx,&by,&cx,&cy,&p);
int i; inv[1]=1;
for(i=2;i<=1e7;i++) inv[i]=mod-(1ll*mod/i*inv[mod%i])%mod;
b[0]=by+1; c[0]=cy+1; f[0]=a;
for(i=1;i<n;i++){
b[i]=(1ll*b[i-1]*bx+by)%p+1, c[i]=(1ll*c[i-1]*cx+cy)%p+1;
f[i]=(1ll*f[i-1]*inv[min(c[i-1],b[max(0,i-2)])]%mod*c[i-1]%mod+f[max(0,i-2)])%mod;
}
f[n]=(1ll*f[n-1]*inv[min(c[n-1],b[max(0,n-2)])]%mod*c[n-1]%mod+f[max(0,n-2)])%mod;
printf("%d\n",f[n]);
return 0;
}Task.2 整除
题目大意：求 \(x^m\equiv x(mod\ n)\) 在 \([1,n]\) 范围内解的个数。\(T\) 组数据，\(n\) 的形式为给出分解好的 \(c\) 个互不相同的且不超过 \(t\) 质数的形式。
数据范围：\(1\leq c\leq 50,t\leq 10^4,m\leq 10^9,T\leq 50\)
数据范围很有启发作用，所以贴一下原题的数据范围：
分类讨论后简化得到的方程就是 \(x^m-x\equiv1(mod\ n)\)。
如果 \(c=1,m=2\ (task_4)\) 的情况就很好处理，\(x-x\equiv 0(mod\ p)\)，这个方程的解就只有 \(1,p\)。
当质数的个数增加，情况并没有变得更复杂。根据中国剩余定理，发现我们要求的是这么个同余方程组：
\[
\begin{cases}
x^m-x\equiv0(mod\ p_1)\\
x^m-x\equiv0(mod\ p_2)\\
\cdot\cdot\cdot\\
x^m-x\equiv0(mod\ p_{c-1})\\
x^m-x\equiv0(mod\ p_c)
\end{cases}
\]
但是直接求快速幂会T，所以筛出来每个质数的次幂。复杂度 \(O(Accepted)\)。
\(Source:\) JZOJ 6272 整除
代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
template<class T>void read(T &x){
x=0; char c=getchar();
while(c<'0'||'9'<c)c=getchar();
while('0'<=c&&c<='9'){x=(x<<1)+(x<<3)+(c^48); c=getchar();}
}
const int N=10050;
const int M=998244353;
int c,m,p,ans;
int pri[N],f[N];
bool vis[N];
int qpow(int a,int b){
int tmp=1,base=a;
while(b){
if(b&1) tmp=(tmp*base)%p;
base=(base*base)%p; b>>=1;
}
return tmp;
}
int cal(int p){
memset(f,0,sizeof(f));
memset(vis,0,sizeof(vis));
vis[1]=1; pri[0]=0; int cnt=2;
for(int i=2;i<p;i++){
if(!vis[i]){
pri[++pri[0]]=i;
f[i]=qpow(i,m);
}
cnt+=(f[i]==i);
for(int j=1;(j<=pri[0])&&(i*pri[j]<p);j++){
vis[i*pri[j]]=1;
f[i*pri[j]]=(1ll*f[i]*f[pri[j]])%p;
if(i%pri[j]==0) break;
}
}
return cnt;
}
int main(){
freopen("division.in","r",stdin);
freopen("division.out","w",stdout);
int T; read(T); read(T);
while(T--){
read(c); read(m); ans=1;
while(c--){
read(p);
ans=(1ll*ans*cal(p))%M;
}
printf("%d\n",ans);
}
return 0;
}Task.3
题目大意：
数据范围：
优质内容筛选与推荐>>1、控件布局通用解决方案
2、[ios2] iOS 滤镜 和 iOS6 中的Core Image技术
3、推广：CF基本辅助V1.1
4、使用Jmeter进行http接口性能测试
5、[后序遍历][堆][倍增] Jzoj P4811