Boxes

2021-08-15

题目大意

有$n$个盒子，每个盒子里装有一个球，它可能是黑色或者白色的概率均为$1/2$。现在你可以花费$C$的价值来获得剩下的所有盒子中剩余的黑色球数量和白色球数量。还可以花费$w[i]$的价值去打开一个盒子。

问：你知道所有盒子中球的颜色的期望花费是多少。题目链接

more >>

展开全文 >>

Double Strings

2021-08-13

题目大意

给定两个字符串A，B，求出满足以下条件的子序列a,b（可以不连续）的数量，并对$10^9+7$取模：

a，b分别来自A，B，且长度$length$相同
$\exist i \in [1,length]$,使得$a_i < b_i$
$\forall j \in [1, i)$,满足$a_j = b_j$。
对于$k \in [i + 1, length]$，$a_k,b_k$没有任何限制。

思路

假如我们已经找到了$A_{a1}...A{a_n}$，和$B_{b_1}...B_{b_n}$相同，那么我们只需要在$A$数组$A_{a_n}$后面中找到一个字母$A_{a_{n+1}}$ ，在$B$数组$B_{b_n}$后面中找到一个字母$B_{b_{n+1}}$，满足$A_{a_{n+1}} < B_{b_{n+1}}$即可，那么剩下的字母就可以随便选了。
假设$A$数组还剩$n$个数可选，$B$数组还剩$m$个可选，那么利用组合数学，就可知道共有$\sum_{i=0}^{min(n,m)} C_n^i + C_m^i$种选法。而此式子等于$C_{n+m}^n$。（具体证明可以参照百度）。~~（蒟蒻不太会）~~
那么剩下的就是统计$A,B$数组有多少个字串是相同的了。我们假设$dp[i][j]$表示在$A$数组前$i$位，$B$数组的前$j$位中共有几个相同的字串，递推时(有点类似与最长公共子序列)：
- 如果$A[i] \not= B[j]$，那么它显然是由$A$数组前$i-1$个字母和$B$数组前$j$个组成，或者是$A$数组前$i$个字母和$B$数组前$j-1$个组成的。但是如果我们直接加上$dp[i-1][j],dp[i][j-1]$的话，会出现多加的情况，那就是$A$数组前$i-1$个字母和$B$数组前$j-1$个组成的,所以我们要再减去$dp[i-1][j-1]$，综上：$dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]$。
- 如果$A[i] = B[j]$，那么它显然也可以由$dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]$得到一部分结果，其他的部分，就是由$A$数组前$i-1$个字母和$B$数组前$j-1$个，再加上$A[i],B[j]$两个字母，即$dp[i-1][j-1]$，其次$A[i],B[j]$两个字母也可以单独作为结果计算，综上：$dp[i][j]=dp[i-1][j]+dp[i][j-1]+1$。
因为结果是要求对结果进行取模的，而且我们的计算中是存在组合数的，所以不能每次都用费马小定理，所以我们需要预处理出阶乘数组和其对应的乘法逆元数组。

代码

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

typedef  long long ll;
const int maxN = 2000005, mod = 1000000007;

ll inv[maxN + 1], f[maxN + 1];

string s1, s2;
long long dp[5005][5005];
int len1, len2;

void exgcd(int a, int b, ll &x, ll &y) //拓展欧几里得
{
    if(b == 0) {
        x = 1; y = 0;
        return ;
    }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}

void init()
{
    f[0] = 1;
    for(int i = 1; i <= maxN; ++i)
        f[i] = f[i - 1] * i % mod; //阶乘数组
    ll x, y;
    exgcd(f[maxN], mod, x, y);
    inv[maxN] = (x % mod + mod) % mod;
    for(int i = maxN - 1; i; --i) {
        inv[i] = inv[i + 1] * (i + 1) % mod; //逆元数组
    }
}

ll C(ll n, ll m)
{
    if(n == m || m == 0)
        return 1;
    if(m > n)
        return 0;
    return (f[n] * inv[m] % mod * inv[n - m] % mod) % mod;
}

int main()
{
    cin >> s1; cin >> s2;
    len1 = s1.length(); len2 = s2.length();
    s1 = " " + s1; s2 = " " + s2;
    init();
    for(int i = 1; i <= len1; ++i) {
        for(int j = 1; j <= len2; ++j) {
            if(s1[i] == s2[j])
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] + 1) % mod;
            else
                dp[i][j] = ((dp[i - 1][j] + dp[i][j - 1]) % mod + mod - dp[i - 1][j - 1]) % mod;
        }
    }
    long long ans = 0;
    for(int i = 1; i <= len1; ++i) {
        for(int j = 1; j <= len2; ++j) {
            if(s1[i] < s2[j]) {
                long long n = len1 - i, m = len2 - j;
                ans = (ans + (dp[i - 1][j - 1] + 1ll) * C(1LL * n + m, 1LL * min(n, m)) % mod) % mod;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

展开全文 >>

KingOfRange

2021-08-11

题目大意

给定一个$n$个数的序列$a_i$。有$q$次询问，每次询问是一个非负整数$k$，求出有多少对$(l, r)$，满足$max(a[i]) - min(a[j]) > k$,其中$l\le i, j \le r$。

more >>

展开全文 >>

OR

2021-08-10

题目大意

给定两个非负数组$b[2...n],c[2...n]$，构造出数组$a[1...n]$满足：$a[i-1]|a[i] = b[i],a[i-1]+a[i]=c[i]$。求出满足要求的数组$a$的数量。$(1\le n \le 10^5, 1\le b[i],c[i] \le 10^9)$

more >>

展开全文 >>

Tree-Xor

2021-08-07

题目大意

给定一棵有n个节点的树，每个节点的权值$a[i]$未知，满足$l[i]\le a[i]\le r[i]$，其中$l[i],r[i]$为给定数值。每条边的权值为已知，其值为它连接的两个边的权值的异或值。求出满足条件的$a[i](1\le i\le n)）$的数量。($1\le n\le 10^5, 1\le l[i] \le r[i]\le 2^{30}$)

more >>

展开全文 >>