trees

一个简单的数学题，只需要将树按高度排序，计算以 ii 为最大值时选取的方案数即可。

#include <bits/stdc++.h>
using namespace std;
struct Rhine_Lab {
    Rhine_Lab()
    {
        freopen("trees.in", "r", stdin);
        freopen("trees.out", "w", stdout);
    }
};
Rhine_Lab Ptilopsis_w;

typedef long long ll;
const int N = 100005;
const int P = 1e9+7;

int n, k;
ll val[N];
ll fact[N], finv[N];

void prework(int n);
ll qpow(ll a, ll b);
ll C(ll n, ll m);


int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++)
        scanf("%lld", &val[i]);
    stable_sort(val+1, val+n+1);
    
    prework(n);
    
    ll ans = 0;
    for(int i = k; i <= n; i++)
    {
        ans += val[i]*C(i-1, k-1)%P;
        ans %= P;
    }
    printf("%lld", ans);
}

ll C(ll n, ll m)
{
    if(n < m) return 0;
    return fact[n] * finv[m]%P * finv[n-m]%P;
}
void prework(int n)
{
    fact[0] = 1;
    for(int i = 1; i <= n; i++)
        fact[i] = fact[i-1]*i%P;
    
    finv[n] = qpow(fact[n], P-2);
    for(int i = n-1; i >= 0; i--)
        finv[i] = finv[i+1]*(i+1)%P;
}
ll qpow(ll a, ll b)
{
    ll ans = 1;
    for(; b; b >>= 1, a = a*a%P)
        if(b&1) ans = ans*a%P;
    return ans;
}

bridge

这题题意有一些不清楚，题目问的是： 从一个特定点开始，可以左右走，最后回到这个点，且每两次经过这个点的时间间隔不超过 mm 。

我们可以用DP搞，设 fif_{i} 表示走 ii 步回到起点且满足时间限制的方案数。

因为向左走和向右走是对称的，所以只计算其中一种然后乘 22 即可。

这时我们需要求出走 2x2x 步回到起点的方案数，且中途不能回到起点。(防止重复)

这个中途不能回到起点比较难计算，我们可以先走一步离开起点，然后计算可以回到起点的方案数，再走一步回来的方案数，将其设为 d2xd_{2x}

所以转移方程就很好写了: fi=∑j=2mfi−j∗dj−2∗2f_i = \sum_{j=2}^{m} f_{i-j}*d_{j-2}*2

因为这是个常系数转移方程，可以矩阵加速递推优化。

#include <bits/stdc++.h>
using namespace std;
struct Rhine_Lab {
    Rhine_Lab()
    {
        freopen("bridge.in", "r", stdin);
        freopen("bridge.out", "w", stdout);
    }
};
Rhine_Lab Ptilopsis_w;

typedef long long ll;
const int P = 1e9+7;

namespace Matrix {
    int lim;
    struct matrix {
        ll a[105][105];
        matrix() { memset(a, 0, sizeof(a)); }
        ll* operator [] (int x) { return a[x]; }
    };
    matrix operator * (matrix a, matrix b)
    {
        matrix c;
        for(int i = 1; i <= lim; i++)
        for(int j = 1; j <= lim; j++)
        for(int k = 1; k <= lim; k++)
            (c[i][j] += a[i][k]*b[k][j]%P) %= P;
        return c;
    }
}
using namespace Matrix;


int n, m;
ll d[105][105];
matrix f, g;

int main()
{
    scanf("%d%d", &n, &m);
    d[0][0] = 1;
    for(int i = 1; i <= m; i++)
    for(int j = 0; j <= i; j++)
    {
        if(j != i) (d[i][j] += d[i-1][j+1]) %= P;
        if(j != 0) (d[i][j] += d[i-1][j-1]) %= P;
    }

    Matrix::lim = m;

    for(int i = 1; i < m; i++)
        g[i+1][i] = 1;
    for(int i = m-1; i >= 1; i--)
        g[i][m] = 2*d[m-i-1][0]%P;
    
    f[1][m] = 1;
    for(; n; n >>= 1, g = g*g)
        if(n&1) f = f*g;

    printf("%lld", f[1][m]);
    
}

flowers

一道规律题，每一位上都有循环节，且第 ii 位的循环节为 2i2^i (不一定是最小循环节)。

这时我们可以枚举每一位，循环的部分直接算就行，剩下的部分就暴力统计即可。

#include <algorithm>
#include <cstdio>
using namespace std;
struct Rhine_Lab {
    Rhine_Lab()
    {
        freopen("flowers.in", "r", stdin);
        freopen("flowers.out", "w", stdout);
    }
};
Rhine_Lab Ptilopsis_w;

typedef long long ll;

ll val, b, n;
ll calc(ll cnt, ll bit);
ll solve(ll a, ll b, ll n);


int main()
{
    int t; scanf("%d", &t);
    while(t --> 0)
    {
        scanf("%lld%lld%lld", &val, &b, &n);
        printf("%lld\n", solve(val, b, n));
    }
}

ll solve(ll a, ll b, ll n)
{
    ll ans = 0;
    ll lowbit = (a&-a);
    ll maxn = b+a*n;
    for(ll i = 1; i < lowbit; i <<= 1)
        ans += n*((b&i)!=0);
    for(ll i = lowbit; i <= maxn; i <<= 1)
        ans += i*(n/(i<<1));
    for(ll i = lowbit; i <= maxn; i <<= 1)
        ans += calc(n%(i<<1), i<<1);
    return ans;
}
ll calc(ll x, ll bit)
{
    ll ans = 0;
    for(ll i = 1; i <= x; i++)
    {
        ll val = (b+val*i)%bit;
        if(val < (bit>>1))
            i = min(x, i + ((bit>>1)-1-val)/val);
        else
        {
            ll r = min(x, i + (bit-1-val)/val);
            ans += r-i+1;
            i = r;
        }
    }
    return ans;
}