T1

枚举T串在S串中的最后一个位置
同时选出T串的方案数是$C_{i-1}^{|T|-1}$，同时规定选出的T串是第一个出现的
那么前面的两个字符之间不能出现第一个字符

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

char s[100005];
int n, m;
ll p = 1e9 + 7, p25[100005], p26[100005], fac[100005], ans;

ll power(ll x, ll y)
{
    ll ret = 1;
    while (y)
    {
        if (y & 1)
            ret = ret * x % p;
        x = x * x % p;
        y >>= 1;
    }
    return ret;
}

ll C(int n, int m)
{
    return fac[n] * power(fac[m], p - 2) % p * power(fac[n - m], p - 2) % p;
}

int main()
{
    freopen("string.in", "r", stdin);
    freopen("string.out", "w", stdout);
    scanf("%s", s + 1);
    cin >> n;
    m = strlen(s + 1);
    p25[0] = p26[0] = fac[0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        p25[i] = p25[i - 1] * 25 % p;
        p26[i] = p26[i - 1] * 26 % p;
        fac[i] = fac[i - 1] * i % p;
    }
    for (int i = 1; i <= n; ++i)
    {
        if (i >= m)
            ans = (ans + C(i - 1, m - 1) * p25[i - m] % p * p26[n - i] % p) % p;
    }
    cout << ans << endl;
    return 0;
}

T2

考虑每个位置上的数对答案的贡献
$\sum_{i=1}^m \frac{A_i}{2^{m-i+1}}$
当底数很大的时候，它对于答案的贡献就可以忽略不计了
用链表维护一个值左右两侧比自己大的数，每次算25次就行了
link

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

struct node
{
    int v, id;
} w[1000005];
int n, Next[1000005], Pre[1000005];
double ans = 0;
bool cmp(node x, node y)
{
    if (x.v == y.v)
        return x.id < y.id;
    return x.v < y.v;
}

int main()
{
    freopen("water.in", "r", stdin);
    freopen("water.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &w[i].v);
        w[i].id = i;
    }
    sort(w + 1, w + n + 1, cmp);
    for (int i = 1; i <= n; ++i)
    {
        Next[i] = i + 1;
        Pre[i] = i - 1;
    }
    for (int i = 1; i <= n; ++i)
    {
        int x = w[i].id;
        int l = x, r = x;
        double tl = 0.0, tr = 0.0, v = 1;
        for (int j = 1; j <= 25; ++j)
        {
            v = v / 2.0;
            if (l)
                tl += v * (l - Pre[l]), l = Pre[l];
            if (r <= n)
                tr += v * (Next[r] - r), r = Next[r];
        }
        ans += 2 * w[i].v * tl * tr;
        Next[Pre[x]] = Next[x];
        Pre[Next[x]] = Pre[x];
    }
    printf("%.15lf\n", ans / n / n);
    return 0;
}

dp

xorequ
CF908G New Year and Original Order
XHXJ’s LIS
find a car 对于一个正整数 n，定义 f(n) 为它十进制下每一位数字的平 方的和。 现在给定三个正整数 $k,a,b$，请求出满足 $a≤n≤b$ 且 $k×f(n) = n$ 的 n 的个数$1≤k,a,b≤10^18$
枚举$f(n)$，带入验证即可

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/cxjy-day-10/