CXJY-Day 10
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/