Codeforces #463 Sol.

Codeforces #463 Sol.

A

给一个串 $ s (|s|\le1000) $,找出任意一个回文串 $ S(|S|\le10000) $ ,使得 $ s $ 是 $ S $ 的子序列。

Sol.

直接输出 $ s+rev(s) $.

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e3 + 10;
char s[maxn];
int main()
{
    scanf("%s", &s);
    int len = strlen(s);
    for(int i = 0; i < len; ++i) putchar(s[i]);
    for(int i = len - 1; ~i; --i) putchar(s[i]);
    return 0;
}

B

$ f(n) $ 为非零的数位之积,

img

求 $g(i)=k,i\in[l,r] $ 的个数。

范围 $ Q \le 2\times10^5,1\le l\le r \le10^6,1\le k\le9 $.

Sol.

打 $ f,g,h(l,k):=\sum_{i\le l} [g(i)=k] $ 的表.

注意数位积与数位和不一样。比赛时我以为 $ g $ 对 $ f $ 满足结合律,实际上是分配律(把数拆成数位之间连接的是加法)。数位和的性质过于良好,等价于在 $ \mod 9 $ 意义下的值,以至于我想当然了。被卡了很久。

要多长点心眼,遇到这种题要把“理所当然”的结论再验证一遍。不过也暴露出我找反例的能力有点弱,应该找最可能出现反例的地方想的。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 1e6 + 10;
int g[maxn], cnt[maxn][10], prod[maxn];
int main()
{
    memset(cnt, 0, sizeof cnt);memset(g, 0, sizeof g);
    for(int i = 1; i < 10; ++i) 
    {
        memcpy(cnt[i], cnt[i - 1], sizeof cnt[i]);
        g[i] = prod[i] = i;
        cnt[i][g[i]] ++;
    }
    for(int i = 10; i < maxn; ++i)
    {
        memcpy(cnt[i], cnt[i - 1], sizeof cnt[i]);
        g[i] = g[prod[i] = prod[i / 10] * (i % 10 == 0 ? 1 : i % 10)];
        cnt[i][g[i]]++;
    }
    int q; read(q);
    while(q--)
    {
        int l, r, k; read(l, r, k);
        printf("%d\n", cnt[r][k] - cnt[l - 1][k]);
    }
    return 0;
}

C

找出 $ P $ 的一个排列,定义img , $ g(i):=\min{j:f(i,j)=i} $.

给定 $ N\le10^6,A,B $ ,使得对所有 $ i\in[1,n],~g(i)=A\text{ or } B $.

Sol.

容易看出这是将一个排列分解为长度为 $ A $ 或 $ B $ 的置换。

解同余方程或者暴力枚出这俩的系数,然后循环移位一下即是合法构造。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
int main()
{
    int n, a, b; read(n, a, b);
    int ti = -1;
    for(int i = 0; i <= n / a; ++i)
    {
        if((n - i * a) % b == 0)
        {
            ti = i;
            break;
        }
    }
    if(ti == -1) {puts("-1"); return 0;}
    int tj = (n - ti * a) / b;
    for(int i = 0; i < ti; ++i) for(int j = 1; j <= a; ++j)
        printf("%d ", i * a + (j) % a + 1);
    for(int i = 0; i < tj; ++i) for(int j = 1; j <= b; ++j)
        printf("%d ", ti * a + i * b + (j) % b + 1);
    return 0;
}

D

初始给一个点 $ 1 $ ,权值为 $ 0 $ 。有两种操作,

  1. 在 $ p $ 下面接一个下一个编号的点,权值为 $ q $.
  2. 询问 $ p $ 的祖先序列中的最长不降权值且和不超过 $ q $ 的长度最长长度。

询问 $ \le 4\times 10 ^5 $, 权值 $ \le 10^{18} $.

Sol.

建一棵按题意形态的原树,一棵新树。原数维护倍增表,找出第一个大于当结点权值的祖先,返回作为其新树的父亲。在新树上同样维护倍增表,询问时二分即可。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 4e5 + 100;
long long ww[maxn];
namespace T1
{
long long w[maxn][20]; int fa[maxn][20];
int check(int u, long long v)
{
    for(int i = 19; ~i; --i) if(w[u][i] < v) u = fa[u][i];
    if(ww[u] >= v) return u; else return fa[u][0];
}
void add(int u, int f)
{
    fa[u][0] = f, w[u][0] = ww[u];
    for(int i = 1; i < 20; ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1], w[u][i] = max(w[fa[u][i - 1]][i - 1], w[u][i - 1]);
}
}
namespace T2
{
int fa[maxn][20], dep[maxn];
long long w[maxn][20];
inline void add(int u, int f)
{
    fa[u][0] = f, w[u][0] = ww[u];
    dep[u] = dep[f] + 1;
    for(int i = 1; i < 20; ++i) fa[u][i] = fa[fa[u][i - 1]][i - 1], w[u][i] = w[u][i - 1] + w[fa[u][i - 1]][i - 1];
}
int check(int u, long long x)
{
    int du = dep[u];
    for(int i = 19; ~i; --i) if(w[u][i] <= x) x -= w[u][i], u = fa[u][i];
    return du - dep[u];
}
}
//long long
int main()
{
    T2::dep[1] = 1;
    int q; read(q);
    long long last = 0, cnt = 1;
    while(q--)
    {
        long long t, p, q; read(t, p, q);  p ^= last, q ^= last;
        if(t == 1)
        {
            ww[++cnt] = q;
            int ti = T1::check(p, ww[cnt]);
            T1::add(cnt, p);
            T2::add(cnt, ti);
        }
        else
        {
            printf("%d\n", last = T2::check(p, q));
        }
    }
    return 0;
}

E

给出 $ n \le 10^9, k\le 5000 $ ,求 $ \sum {n \choose i} i ^k $.

Sol. 1

我们注意到和这个形式相像的式子即为二项式展开 $ (1+x)^n=\sum {n \choose i} x^i $。

这启发我们一定可以从这个式子变形得到原式,我们考虑求导补次,即 $ x[(1+x)^n]' = \sum {n \choose i} ix^{i} $。

发现如此操作 $ k $ 次后得到的式子令 $ x=1 $ 即为我们需要的答案。

我们有 $ x {\mathrm{d}\over\mathrm{d}x} (x^a(1+x)^b) = ax^a(1+x)^b+bx^{a+1}(1+x)^{b-1} $ ,写出递推方程,$ f_{k,a,b} = af_{k-1,a,b}+bf_{k-1,a+1,b-1} $ ,记忆化搜索一遍可得答案,注意判断 $ a,b $ 为 $0 $ 的情况。

这个虽然看起来时是三维的,但注意到后两维和为定值,这降了一维。

Sol. 2

继续沿用求导的思路,但我们不补次,于是得到 $ [(1+x)^n]^{(k)} = n^{\underline k}(1+x)^{n-k}=\sum{n \choose i} i^{\underline k}x^{i-k} $.

一个自然而然的想法是使用第二类把幂表示成下降幂,即 $ \sum \left{ \begin{matrix} n \ k\end{matrix} \right} x^{\underline k} = x^n $.

从而 $ \sum_i {n \choose i} i^k = \sum_i{n \choose i}\sum_j \left{\begin{matrix}k \ j\end{matrix}\right} i^{\underline j} = \sum_j \left{\begin{matrix}k \ j\end{matrix}\right} \sum_i {n \choose i}i^{\underline j} = \sum_j \left{\begin{matrix}k \ j\end{matrix}\right} [n^{\underline j}(1+x)^{n-j}]_{x=1} $.

第二类可以 $ O(k^2) $ 预处理,下降幂 $ O(k) $ 预处理,$ 2 $ 的幂 $ O(\lg n) $ 直接计算。总的复杂度仍然是 $ O(k^2) $.

同样注意 $ n-j $ 小于等于 $ 0 $ 的情况。

Code 1

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 5000 + 10, mod = 1e9 + 7;
long long power(long long a, long long b)
{
    long long ret = 1;
    for(; b; b >>= 1, (a *= a) %= mod) if(b & 1)
        (ret *= a) %= mod;
    return ret;
}
long long dp[maxn][maxn];
long long cal(int k, int a, int n)
{
    if(~dp[k][a]) return dp[k][a];
    if(k == 0) return dp[k][a] = power(2, n - a);
    int b = n - a;
    return dp[k][a] = ((a ? 1ll * (a) % mod * cal(k - 1, a, n) % mod : 0) + (b ? 1ll * (b) % mod * cal(k - 1, a + 1, n) % mod : 0)) % mod;
}
int main()
{
    int n, k; read(n, k);
    memset(dp, -1, sizeof dp);
    printf("%d\n", cal(k, 0, n));
}

Code 2

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int mod = 1e9 + 7, maxn = 5000 + 5;
long long power(long long a,long long b){long long ret = 1;for(; b; b >>= 1, (a *= a) %= mod) if(b & 1) (ret *= a) %= mod; return ret;}
long long S[maxn][maxn], D[maxn];
int main()
{
    int n, k; read(n, k);
    S[0][0] = 1;
    for(int i = 1; i <= k; ++i) for(int j = 1; j <= i; ++j)
        S[i][j] = (S[i - 1][j - 1] + j * S[i - 1][j] % mod) % mod;
    D[0] = n;
    for(int i = 1; i <= k; ++i) D[i] = (n - i) * D[i - 1] % mod;
    int ret = 0;
    for(int i = 1; i <= min(n, k); ++i)
        (ret += S[k][i] * D[i - 1] % mod * power(2, n - i) % mod) %= mod;
    printf("%d\n", ret);
    return 0;
}

标签: none

添加新评论

bst g22 jinniu lilai opebet orange88 vinbet xbet yuebo zunlong shijiebei bet007 hg0088 ju111 letiantang m88 mayaba qg777 qianyiguoji sbf777 tengbohui tlc ule weilianxier waiweitouzhu xingfayule xinhaotiandi yinheyule youfayule zhongying 2018shijiebei w88 18luck 188bet beplay manbet 12bet 95zz shenbo weide1946 ca88 88bifa aomenxinpujing betway bodog bt365 bwin tongbao vwin weinisiren 88jt fenghuangyule hongyunguoji 918botiantang huanyayule jianada28 jixiangfang libo long8 hongzuyishi zuqiutouzhu