给出整数n和r。求区间[1;r]中与n互素的数的个数。
1

题目数据量很大，不能暴力枚举。
解决他的逆问题，求不与n互素的个数。
考虑n的所有素因子pi（i=1...k)
在[1;r]中有多少数能被pi整除呢？它就是：r/pi。
但是我们不能单纯的让所有结果相加，因为有很多数可以被统计很多次，所以这时候用到容斥定理来处理。
1
2
3
4
5

int solve (int n, int r)
{
    vector p;
    for (int i=2; i*i<=n; ++i)
        if (n % i == 0)
        {
            p.push_back (i);
            while (n % i == 0)
                n /= i;
        }
    if (n > 1)
        p.push_back (n);

    int sum = 0;
    for (int msk=1; msk<(1<

• 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

四、概率dp， 期望dp

4.1概率

概率加法

1. 互不相交的事件，P(A或B发生)=P(A)+P(B)
2. 如果A和B所涵盖的结果有交集，那么P(A或B发生)=P(A)+P(B)-P(A与B同时发生)

概率乘法

1. 在两个 互不干扰的事中，事件A在其中一件事中，事件B在另外一件事中

   那么P(A与B同时发生)=P(A)P(B)

2. 掷两个骰子，P(第一个点数小于3且第二个点数为偶数)=(2/6)(3/6)=1/6

4.2期望

1. 事件A有多种结果，记其结果的大小为x，那么x的期望值表示 事件A 的结果的平均大小，记作E(x)。

2. E(x)=每种结果的大小与其概率的乘积的和。

   例如，记掷一枚骰子的点数为x

   E(x)=1*(1/6)+2*(1/6)+3*(1/6)+4*(1/6)+5*(1/6)+6*(1/6)=7/2

3. 若c为常数，那么：
   E(x+c)=E(x)+c，E(c*x)=c * E(x)

4. 期望加法-----期望线性 性
   记两个事件的结果分别为x,y
   E(x+y)=E(x)+E(y)
   例如：E(语文成绩+数学成绩)=E(语文成绩)+E(数学成绩)

4.3概率与期望dp

概述

由于概率和期望具有线性性质，使得可以在概率和期望之间建立一定的递推关系，这样就可以通过动态规划来解决一些概率问题，例如概率和期望的最值问题就常常使用概率 DP、期望 DP 来解决。

概率dp

概率 DP 通常已知初始的状态，然后求解最终达到目标的概率，因此概率 DP 需要顺序求解。

其相较于期望 DP较为简单，当前状态只需加上所有上一状态乘上转移概率即可，即：f[i]=f[i-1]*p[i]

期望 dp

期望 DP 与概率 DP 不同，其需要倒序求解。

当求解达到某一目标的期望花费时，由于最终的花费无从知晓（无法从无穷推起），因此期望 DP 需要倒序求解。

设 f[i] 为 i 状态下实现目标的期望值，即到了 f[i] 这个状态的差距是多少。

初始时，令 f[n]=0，即在目标状态期望值为 0，然后进行状态转移，新的状态为上一状态与转移概率的乘积再加上转移的花费

即：*f[i-1]=f[i]p[i]+w

最后初始位置 f[0] 即为所求的期望值。

例题

题意：给定一个n面的骰子，问投出n个不同的面的期望投掷次数。 （1<=n<=1000）

分析：先考虑逆向转移,dp[n]=0 表示投出n个不同面之后，要达到投出n个不同面的状态还需要投掷0次。

即：dp[i]表示已经投出了i个面，要投出剩余n-i面的期望次数。

对于当前状态为i，投一次骰子，有i/n的可能投中已经出现的i个面之一，此情况下还需要投dp[i]次
					   有(n-i)/n的可能投出其余n-i面。此情况下还要投dp[i+1]次
即：由于投出的面可能出现过，也可能没出现过，所以dp[i]由dp[i] 与 dp[i+1] 转移而来
dp[i]=dp[i]*(i/n) + dp[i+1]*((n-i)/n) +1   （+1是因为要投一次骰子才能转移）
移项变成：dp[i]=dp[i+1] + n/(n-i)
1
2
3
4
5

#include
using namespace std;
#define ll long long
#define pii pair
const int maxn = 2e3+5;
const int mx = 40;
const int mod = 1e9+5;
const ll inf = 34359738370;
const int INF = 1e9+7;
//给定n面的骰子 求投的期望次数 满足每面都至少出现一次
double dp[maxn];//dp[i] 表示已经出现i个面时  投出剩余n-i面的期望次数 dp[n]=0
//再投一次 i/n的几率投中已经有的面，此情况下还需要投dp[i]次骰子，(n-i)/n几率投中新的面  此情况下还要投dp[i+1]次
//dp[i]=(i/n)dp[i] + (n-i)/n *dp[i+1] +1
//(n-i)/n * dp[i]= (n-i)/n *dp[i+1] +1
//dp[i]=dp[i+1] + n/(n-i)
int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        dp[n]=0.0;
        for(int i=n-1;i>=0;--i)
        {
            dp[i]=dp[i+1] + 1.0*n/(n-i) ;
        }
        printf("%.2f\n",dp[0]);
    }
    return 0;
}
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

板子

一、排列组合数

1、费马小定理（要求模数为质数）

复杂度O(nlogn)，当n到1e7时就炸，这时候要用线性递推。

typedef long long ll;
const ll maxn = 1e6+10, mod = 1e9+7;
ll Jc[maxn];
void calJc()    //求maxn以内的数的阶乘
{
    Jc[0] = Jc[1] = 1;
    for(ll i = 2; i < maxn; i++)
        Jc[i] = Jc[i - 1] * i % mod;
}
ll pow(ll a, ll n, ll mod)    //快速幂 a^n % p
{
    ll ans = 1;
    while(n)
    {
        if(n & 1) ans = ans * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return ans;
}
ll niYuan(ll a)   //费马小定理求逆元
{
    return pow(a, mod - 2, mod);
}
ll C(ll n, ll r)    //计算C(n, r)
{
    if(r>n)return 0;
    return Jc[n] * niYuan(Jc[r]) % mod
        * niYuan(Jc[n - r]) % mod;
}
ll A(ll n, ll r)
{
    return Jc[n] * niYuan(Jc[n-r])%mod;
}
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

2、拓展欧几里得（不要求模数为质数）

复杂度同上，关键点在他的模数不需要是质数。

typedef long long ll;
const ll maxn = 1e6+10, mod = 1e9+7;
ll Jc[maxn];
void calJc()    //求maxn以内的数的阶乘
{
    Jc[0] = Jc[1] = 1;
    for(ll i = 2; i < maxn; i++)
        Jc[i] = Jc[i - 1] * i % mod;
}
void exgcd(ll a, ll b, ll &x, ll &y)    //拓展欧几里得算法
{
    if(!b) x = 1, y = 0;
    else
    {
        exgcd(b, a % b, y, x);
        y -= x * (a / b);
    }
}
ll niYuan(ll a)   //求a对b取模的逆元
{
    ll x, y;
    exgcd(a, mod, x, y);
    return (x + mod) % mod;
}
ll C(ll n, ll r)    //计算C(n, r)
{
    if(r>n)return 0;
    return Jc[n] * niYuan(Jc[r]) % mod
        * niYuan(Jc[n - r]) % mod;
}
ll A(ll n, ll r)
{
    return Jc[n] * niYuan(Jc[n-r])%mod;
}
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

3、逆元-线性递推(p是质数)

typedef long long ll;
const ll maxn = 1e7+10, mod = 1e9+7;
ll Jc[maxn];
ll inv[maxn+5];
void getInv(ll mod)
{
    inv[1]=1;
    for(int i=2;in)return 0;
    return Jc[n] * inv[Jc[r]] % mod
        * inv[Jc[n - r]] % mod;
}
ll A(ll n, ll r)
{
    return Jc[n] * inv[Jc[n-r]]%mod;
}
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

4、Lucas定理

typedef long long ll;
const ll maxn = 1e6+10, mod = 1e9+7;
ll Jc[maxn];
void calJc()    //求maxn以内的数的阶乘
{
    Jc[0] = Jc[1] = 1;
    for(ll i = 2; i < maxn; i++)
        Jc[i] = Jc[i - 1] * i % mod;
}
void exgcd(ll a, ll b, ll &x, ll &y)    //拓展欧几里得算法
{
    if(!b) x = 1, y = 0;
    else
    {
        exgcd(b, a % b, y, x);
        y -= x * (a / b);
    }
}
ll niYuan(ll a)   //求a对b取模的逆元
{
    ll x, y;
    exgcd(a, mod, x, y);
    return (x + mod) % mod;
}
ll C(ll n, ll r)    //计算C(n, r)
{
    if(r>n)return 0;
    return Jc[n] * niYuan(Jc[r]) % mod
        * niYuan(Jc[n - r]) % mod;
}
ll A(ll n, ll r)
{
    return Jc[n] * niYuan(Jc[n-r])%mod;
}
ll Lucas(ll n,ll r)
{
    if(n