C

一个环,有n个位置,每个位置的数给定一个取值范围,等概率取范围内的整数,给一个质数p,若相邻两个数的积被p整除,则每个可以获得1000元,求获得钱数的期望。

概率
我们很容易求出每个位置取被p整除的数的概率,而p是质数,所以必须两个位置都被p整除才可以获得2000元
所以我们扫一遍,每两个位置求一次。 复杂度$O(n)$

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn = 1e5 + 10;
int n,p;
int l[maxn],r[maxn];
double rng[maxn];


int main()
{
//freopen("test.txt","r",stdin);
scanf("%d %d",&n,&p);
for(int i=0;i<n;++i) scanf("%d %d",l+i,r+i);
l[n] = l[0]; r[n] = r[0];
for(int i=0;i<=n;++i)
rng[i] = (double)((r[i]/p) - ((l[i]-1)/p))/(r[i]-l[i]+1);
double ans = 0;
for(int i=1;i<=n;++i)
{
//printf("%d %lf\n",i-1,rng[i-1]);
ans += 2*(rng[i-1]*rng[i] + (1-rng[i-1])*rng[i] + rng[i-1]*(1-rng[i]));
}
printf("%.12lf\n",ans*1000);
return 0;
}

D

给12个关于$x,y,z$的式子,输入$x,y,z$求式子中最大的一个

乱搞
只要解决精度问题就行了,由于产生的数很大,所以我们开个log然后比较
注意不能开两个log,因为$log(x)$有可能为负数,$log(log(x))$就会出错
而开一个log又在long double范围内

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double LDB;

const char ans[13][10] = {"x^y^z","x^z^y","(x^y)^z","(x^z)^y","y^x^z","y^z^x","(y^x)^z","(y^z)^x","z^x^y","z^y^x","(z^x)^y","(z^y)^x"};

LDB cal(int op,LDB x,LDB y,LDB z)
{
LDB res = 0;
switch(op){
case 0: res= pow(y,z)*log(x);break;
case 1: res= pow(z,y)*log(x);break;
case 2:
case 3: res = y*z*log(x);break;

case 4: res= pow(x,z)*log(y);break;
case 5: res= pow(z,x)*log(y);break;
case 6:
case 7: res = x*z*log(y);break;

case 8: res=pow(x,y)*log(z);break;
case 9: res=pow(y,x)*log(z);break;
case 10:
case 11: res = x*y*log(z);break;
}
return res;
}

int main()
{
//freopen("test.txt","r",stdin);
LDB a,b,c;
cin>>a>>b>>c;
LDB res = cal(0,a,b,c);
int cur = 0;
for(int i=1;i<12;++i)
{
LDB val = cal(i,a,b,c);
// cout<<val<<" "<<i<<endl;
if(res < val)
{
res = val;
cur = i;
}
}
// cout<<cur<<'\n';
cout<< ans[cur] << '\n';
return 0;
}

E

有n个数(1-9),我们每次任选一个,选择一个长度为b位的数,求这个数除x余k的方案数。

矩阵快速幂
我们构造一个$x*x$的矩阵$M_{ij}$表示上一位余数为i,转移到这一位余数为j($j = (i*10+j)%x $)的方案数

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const LL mod = 1e9 +7;
const int maxn = 110;
int n,N,b,k,x;
int cnt[12];

struct Matrix
{
LL m[maxn][maxn];

void clear()
{
memset(m,0,sizeof m);
}

void init()
{
memset(m,0,sizeof m);
for(int i=0;i<n;++i) m[i][i]=1;
}

void print()
{
for(int i=0;i<n;++i){
for(int j=0;j<n;++j)
printf("%d ",m[i][j]);
puts("");
}
}

Matrix operator+(const Matrix rhs) const
{
Matrix t;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
t.m[i][j] = (m[i][j] + rhs.m[i][j]) % mod;
return t;
}

Matrix operator*(const Matrix rhs) const
{
Matrix c;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
{
c.m[i][j] = 0;
for(int k=0;k<n;++k)
c.m[i][j] = (c.m[i][j] + m[i][k] * rhs.m[k][j]) % mod;
}
return c;
}

Matrix operator^(int n) const
{
Matrix a,b;
a = *this;
b.init();
while(n)
{
if(n&1) b = b*a;
n>>=1;
a = a*a;
}
return b;
}


} M,A;

int main()
{
//freopen("test.txt","r",stdin);
scanf("%d %d %d %d",&N,&b,&k,&x);
n = x;
memset(cnt,0,sizeof cnt);
for(int i=0;i<N;++i)
{
int x;
scanf("%d",&x);
++cnt[x];
}
M.clear();
for(int j=0;j<x;++j)
{
for(int z=1;z<=9;++z)
{
M.m[(j*10 + z)%x][j] += cnt[z];
}
}
A.clear();
A.m[0][0] = 1;
M = M^b;
A = M*A;
printf("%lld\n",A.m[k][0]);
return 0;
}