有趣的序列
洛谷链接
这一道题是一道卡特兰数的题，但是因为数据量以及要进行模运算的原因，要采用我先前博客中写到的通项式。当然因为不可以直接算阶乘，因此采取分解阶乘的方法转换成乘法。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include<bits/stdc++.h>
#define maxn 1000002
#define Int64 long long
using namespace std;
int primes[2*maxn];
int sum[2*maxn];
bool isp[2*maxn];
int newp=0;
void Eular_Sieve(){
for(int i=2;i<2*maxn;i++){
if(!isp[i]){
primes[++newp]=i;
}
for(int j=1;j<=newp&&primes[j]*i<2*maxn;j++){
isp[primes[j]*i]=true;
if(!(i%primes[j]))break;
}
}
return;
}
Int64 qkpow(int a,int b,int p){
if(b==1)return a;
if(b%2){
Int64 t=qkpow(a,b/2,p);
t=t*t%p;
t=t*a%p;
return t;
}
else {
Int64 t=qkpow(a,b/2,p);
t=t*t%p;
return t;
}
}
int n,p;
int main(){
scanf("%d%d",&n,&p);
Eular_Sieve();
for(int i=1;i<=newp;i++){
Int64 t=primes[i];
Int64 cnt1=0,cnt2=0,cnt3=0;
while(t<=2*n){
cnt1+=(2*n/t);cnt2+=((n+1)/t);cnt3+=(n/t);
t*=primes[i];
}
sum[i]=cnt1-cnt2-cnt3;
}
Int64 ans=1;
for(int i=1;i<=newp;i++){
if(sum[i]){
(ans*=qkpow(primes[i],sum[i],p))%=p;
}
}
printf("%lld",ans);
return 0;
}
|
打气球
这道题我就不给网址了，yzoj上面最后一页找
题目描述
Descrition
周末何老板到磁器口游玩。街边有小贩在组织一种打气球游戏，何老板很感兴趣。
店家立了一块布，布上画了N*N的方格，有的方格里挂上了气球，有的没有。
游戏规则如下：
第1步.观察。如果每一行都至少有一个方格没有气球，并且每一列都至少有一个方格没有气球，游戏结束。否则进行第2步。
第2步.抛骰子。店家拿出一个特制的骰子，该骰子有N个面，上面依次有1到N这N 个数字。玩家先后抛两次骰子，设第一次抛出的数字为x，设第二次抛出的数字为y (注：抛出的数字是随机的)。
第3步.打气球。若坐标为(x,y)的格子里有气球，玩家必须将其打爆。子弹1块钱一发。
如果该格子没有气球，忽略该格子，玩家不用开枪，但玩家也需要支付给店家1块钱。
第4步.继续。执行第1步。
何老板是个神枪手，他能做到百发百中。他想你帮他算算，对于当前给出的这局游戏，预计要花多少钱才能结束。
Input
第一行，两个整数N和M，N表示方格的尺寸,M表示游戏开始时，有M个格子里是没有气球的。 接下来M行，每行两个整数x,y,表示坐标为x,y的格子里没有气球。
Output
一行，一个实数，完成游戏预计花费，保留2个小数位。
Sample Input
Sample Output
如果你想看更多的样例输出，可以去WYX大佬的博客
分析
这一道题啊，实际上啊，就是一道期望的题，如果你点开了上面的那一个链接，多半也看见了YB说的话了吧，那么接下来要做的事情就是找出递归的关系
首先，我们都知道每一个格子概率为$\frac{1}{n^2}$
我们设有$r$行已经打掉，$c$列已经打掉，函数为$f[r][c]=……$
那么分类讨论
1.如果说没有抽到有气球的地方，那么就是他自己乘上没有气球的地方的概率
2.如果说打掉的地方只能消除行，那么就是乘上$f[r-1][c]$以及这些地方的概率，只能消除列同理
3.如果可以同时消去的话，那么就可以类比上面的，写出式子来。
4.当然最后你应该加上1，因为每打一次收费1
式子和化简如下
$$
f[r][c]=\\ \frac{f[r-1][c]\times r(n-c)+f[r][c-1]\times c(n-r)+f[r-1][c-1]\times r\times c+f[r][c]\times(n-r)(n-c)+n^2}{n^2(n-r)(n-c)}
$$
好了，既然已经知道了式子，那么就可以比较容易的做出来了，至于边界，那你也可以自己推出来，你可以选择两种方法，$dfs$ or$ dp$
我的代码里面把$dfs$的注释掉了
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include<bits/stdc++.h>
#define maxn 2003
using namespace std;
double f[maxn][maxn];
bool row[maxn],col[maxn];
int n,m;
double dfs(int r,int c){
double ans=0;
if(!r&&!c)return 0;
if(f[r][c]!=-1)return f[r][c];
if(r)ans+=dfs(r-1,c)*r*(n-c);
if(c)ans+=dfs(r,c-1)*c*(n-r);
if(r&&c)ans+=dfs(r-1,c-1)*r*c;
return f[r][c]=(double)(ans+n*n)/(n*(c+r)-c*r);
}
int main(){
scanf("%d%d",&n,&m);
int r=n,c=n;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
if(!row[x])r--,row[x]=true;
if(!col[y])c--,col[y]=true;
}
for(int i=1;i<=n;i++){
f[i][0]=f[i-1][0]+n/(i+0.0);
f[0][i]=f[0][i-1]+n/(i+0.0);
}
for(int i=1;i<=r;i++){
for(int j=1;j<=c;j++){
double tmp=f[i-1][j]*i*(n-j)+f[i][j-1]*(n-i)*j+f[i-1][j-1]*i*j+n*n;
f[i][j]=tmp/(n*(i+j)-i*j);
}
}
printf("%.2lf",f[r][c]);
return 0;
}
|
还有一道题，不过比较水，居然用暴力枚举就可以做出来了，早知道我当时就直接枚举了，题目与韩信点兵类似