【luoguP3239】[HNOI2015]亚瑟王

严重自闭ing
这个题首先一个直接想法是设dp_{i,j}表示目前考虑到第i个人,恰好在第j轮发动技能的概率……然后就发现这样没法转移了,因为一堆概率都是互相关联的,存在后效性。
考虑一个莫得后效性的状态,设dp_{i,j}表示考虑了前i个人,有j个发动技能的代价,那么dp_{i,j}只会和dp_{i-1,j-1},dp_{i-1,j}有关系,这个人单算不发动技能的概率是(1-p_i)^{r-j},相反的,发动技能的概率就是1-(1-p_i)^{r-j}
因此状态转移式子为

dp_{i,j} = dp_{i – 1, j} \cdot (1-p_i)^{r-j} + dp_{i – 1, j – 1} \cdot (1-(1-p_i)^{r-j})

那么对于每个人来说,发动技能的概率就是

P_i = \sum_{j = 0}^{i – 1}dp_{i-1, j} \cdot (1 – (1 – p_i)^{r – j})

最后答案就是

ans = \sum_{i = 1}^n P_i \cdot d_i

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <bitset>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

template <typename int_qwq>

inline void re(int_qwq &x)
{
    x = 0;
    char a;
    bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b)
        x = - x;
}

int T, n, r, d[225];

double dp[225][140], p[225], P[225][225];

int main()
{
    cin >> T;
    while(T --)
    {
        cin >> n >> r;
        for(ri i = 1; i <= n; i ++)
            cin >> p[i] >> d[i];
        memset(dp, 0, sizeof(dp)), memset(P, 0, sizeof(P));
        for(ri i = 1; i <= n; i ++)
        {
            P[i][0] = 1;
            for(ri j = 1; j <= r; j ++)
                P[i][j] = P[i][j - 1] * (1 - p[i]);
        }
        dp[0][0] = 1;
        for(ri i = 1; i <= n; i ++)
            for(ri j = 0; j <= min(i, r); j ++)
            {
                dp[i][j] = dp[i - 1][j] * P[i][r - j];
                if(j > 0)
                    dp[i][j] += dp[i - 1][j - 1] * (1 - P[i][r - j + 1]);
            }
        double pri = 0.0;
        for(ri i = 1; i <= n; i ++)
        {
            double tmp = 0.0;
            for(ri j = 0; j < min(i, r); j ++)
                tmp += dp[i - 1][j] * (1 - P[i][r - j]);
            pri += tmp * d[i];
        }
        printf("%.10lf\n", (double)pri);
        //cout << pri << '\n';
    }
}

【算法】杜教筛&二项式反演&莫比乌斯反演

在此之前,狄利克雷卷积
(f·g)(n) = \sum_{d|n}f(d)g(\frac{n}{d})
积性函数嘛……虽然看起来像是完全积性函数……记住就好了。
但是一般我们并不真的直接这么看,我们会想办法把d|n变成\lfloor \frac{n}{d} \rfloor
然后再扯两个比较常见的,狄利克雷卷积结果
\sum_{d|n}\mu(d) = [n=1] = (\mu · 1) = e
\sum_{d|n}\phi(d) = n = (\phi · 1) = id
接下来,开始杜教筛。

杜教筛

假如有一个积性函数f(i),现在我们要求它的前缀和,即\sum_{i=1}^{n}f(i)
杜教筛的目的是,通过将原有的函数卷上别的函数,得到一个比较好算的狄利克雷卷积形式,加速运算。
我们先写一个普通形式

\sum_{i=1}^{n}\sum_{d|i}g(d)f(\frac{i}{d})

然后交换求和顺序,将d提前

\begin{aligned} \sum_{d=1}^{n}g(d)\sum_{d|i}f(\frac{i}{d}) &= \sum_{d=1}^{n}g(d)\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}f(i)\\ &= \sum_{d=1}^{n}g(d)S(\lfloor \frac{n}{d} \rfloor) \end{aligned}

这里我把i的含义换成了\frac{i}{d}
那么

g(1)S(n) = \sum_{i=1}^{m}(f·g)(i)-\sum_{d=2}^{n}g(d)S(\lfloor \frac{n}{d} \rfloor)

假如\sum_{i=1}^{m}(f·g)(i)这个式子可以在一个较为快速的时间里面计算,那么我们就可以递归地套数论分块计算\sum_{d=2}^{n}g(d)S(\lfloor \frac{n}{d} \rfloor)这个式子。
假如f(i)=\mu(i),那么根据之前的一个狄利克雷卷积结果

\sum_{d|n}\mu(d) = [n=1] = (\mu · 1) = e

g(i)换成1(i)

\sum_{i=1}^{m}(f·g)(i)=1

这实际上是对于[i=1]求了个前缀和。
所以最后的公式就是

S(n)=1-\sum_{d=2}^{n}S(\lfloor \frac{n}{d} \rfloor)

\mu(i)换成\phi(i),那么利用第二个结论

\sum_{d|n}\phi(d) = n = (\phi · 1) = id

g(i)=1(i)这个不动,但是前面发生了改变

S(n)=\frac{n(n-1)}{2}-\sum_{d=2}^{n}S(\lfloor \frac{n}{d} \rfloor)

杜教筛可以通过处理n较小的部分加速运算,这样做的复杂度大概会到n^{\frac{2}{3}}这样的级别左右。

二项式反演

二项式反演一共有两个形式

f(n) = \sum_{i=0}^{n} (-1)^i C_n^i g(i) \Leftrightarrow g(n)=\sum_{i=0}^n (-1)^i C_n^i f(i)

f(n) = \sum_{i=0}^{n} C_n^i g(i) \Leftrightarrow g(n)=\sum_{i=0}^n (-1)^{n-i} C_n^i f(i)

只推一下第一个吧

\begin{aligned} g(n) &= \sum_{i=0}^n(-1)^iC_n^i\sum_{j=0}^{i}(-1)^jC_i^jg(j)\\ &= \sum_{j=0}^ng(j)\sum_{i=j}^nC_n^iC_j^i(-1)^{i+j} \end{aligned}

\begin{aligned} g(n) &= \sum_{j=0}^{n}C_n^jg(j)\sum_{i=0}^{n-j}C_{n-j}^{n-i}(-1)^{i+2j}\\ &= \sum_{j=0}^{n}C_n^jg(j)(1-1)^{n-j}\sum_{i=0}^{n-j}C_{n-j}^{n-i}(-1)^{i} \end{aligned}

到这里其实已经很明显了,后面部分是二项式定理的展开,也就说

g(n)=\sum_{j=0}^{n}C_n^jg(j)(1-1)^{n-j}

只有j=n的时候这个式子才不为0,也就说g(n)=g(n),得证。
[BZOJ 2839]集合计数
g(k)表示目前有交集的元素个数为k并且符合条件的方案数,f(k)表示重合元素至少有k个符合条件的方案数。
那么,f(k)=C_n^k(2^{2^{n-k}}-1)
这个2^{2^{n-k}}-1,幂次上的2^{n-k}是考虑固定之后所有的集合,下面的2表示每个集合选不选,这个时候一定要选择一个集合。
但是这样会存在重复的情况,比如你选定了2,3这两个元素被重合,但事实上重合的部分是2,3,4,这个时候就会产生错误的计算了。
因此你要减去k+1个元素被选定的情况,然而你发现k+2的情况被多选择了,因此最后写出来是这样的
g(k)=\sum_{i=k}^{n}(-1)^{i-k}C_i^kf(i)
然后O(n)算就好了……我也不知道为什么qb的老师会放在二项式反演。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const lo mo = 1000000007;

lo n, k, ans, fac[1000010], inv[1000010];

inline lo ksm(lo x, lo K, lo Mo)
{
    lo rt = 1, a = x;
    while(K)
        rt = rt * ((K & 1) ? a : 1) % Mo, a = a * a % Mo, K >>= 1;
    return rt;
}

int main()
{
    re(n), re(k);
    fac[1] = inv[1] = fac[0] = inv[0] = 1;
    for(ri i = 2; i <= n; i ++)
        fac[i] = fac[i - 1] * i % mo;
    inv[n] = ksm(fac[n], mo - 2, mo);
    for(ri i = n - 1; i > 1; i --)
        inv[i] = inv[i + 1] * (i + 1) % mo;
    for(ri i = k; i <= n; i ++)
    {
        lo tmp = fac[n] * inv[i] % mo * inv[n - i] % mo * (((ksm(2, ksm(2, (n - i), mo - 1), mo) - 1) % mo + mo) % mo) % mo;
        tmp = tmp * fac[i] % mo * inv[k] % mo * inv[i - k] % mo;
        if((i - k) & 1)
            ans = ((ans - tmp) % mo + mo) % mo;
        else
            ans = (ans + tmp) % mo;
    }
    printf("%lld", ans);
}

【luoguP4221】[WC2018]州区划分

这个题目比较考察科技啊。

首先让我们考虑最暴力的状态方程,设dp_{s}表示目前所有已经被选择的城市集合为s,这样的满意度之和。那么方程为
dp_{s}=\frac{1}{sum_s}\sum_{T\in s}dp_{T}sum_{s-T}

之所以乘\sum_{s-T}是为了抵消原来的分母的影响。这里默认sum都是p次方之后的。

那么现在这个东西首先可以枚举子集来做,复杂度O(3^n),t到不知道哪里去了,接下来怎么办?

注意到后面这个式子,实际上他相当于满足T \; and \; (s-T) = 0,T \; or \; (s-T) = s

那么这个东西就相当Ts-T二进制上的1加起来正好等于s上的1个数,且T \; xor \; (s-T) = s这么一个情况,那么我们多加一维限制,分层fwt。

注意sum就不要逆变换回去了,并且dp值除了最后都要保证一直fwt,正变换之后和fft结果类似,可以O(n)乘起来,还要注意fwt不要带乘法,能换成加减就别用乘法和取模,这破题卡常

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

typedef unsigned int uint;

template<typename inp_typ>

inline void re(inp_typ &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 23;

const int mo = 998244353, inv2 = 499122177;

int lx, fa[ms], ly, n, m, p, de[ms];

int w[ms], su[3000030], dp[ms][3000030], vx[ms][3000030];

struct edge
{
    int x, y;
}e[1010];

inline int ksm(lo x, lo k)
{
    lo rt = 1, a = x;
    while(k)
        rt = rt * ((k & 1) ? a : 1) % mo, a = a * a % mo, k >>= 1;
    return (int)rt;
}

inline int ask(int x)
{
    int rt = 0;
    while(x)
        x -= (x & (-x)), rt ++;
    return rt;
}

int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

inline bool check(int s)
{
    for(ri i = 1; i <= n; i ++)
        fa[i] = i, de[i] = 0;
    int cnt = ask(s), fx, fy;
    for(ri i = 1; i <= m; i ++)
        if(((1 << (e[i].x - 1) & s)) && (((1 << (e[i].y - 1)) & s)))
        {
            de[e[i].x] ++, de[e[i].y] ++, fx = find(e[i].x), fy = find(e[i].y);
            if(fx != fy)
                fa[fx] = fy, cnt --;
        }
    if(cnt > 1)
        return 1;
    for(ri i = 1; i <= n; i ++)
        if(((1 << (i - 1)) & s) && (de[i] & 1))
            return 1;
    return 0;
}

inline int add(int x, int y)
{
    x += y, x -= (x >= mo) ? mo : 0;
    return x;
}

inline void fwt(int *a, int len, int tp)
{
    /*int la, lb;
    for(ri i = 1; i < len; i <<= 1)
        for(ri j = 0; j < len; j += (i << 1))
            for(ri k = j; k < j + i; k ++)
            {
                la = a[k], lb = a[k + i];
                a[k] = add(la, lb), a[k + i] = add(la, mo - lb);
                if(tp == -1)
                    a[k] = 1ll * a[k] * inv2 % mo, a[k + i] = 1ll * a[k + i] * inv2 % mo;
            }*/
    for(ri i = 1; i < len; i <<= 1)
        for(ri j = 0; j < len; j += (i << 1))
            for(ri k = 0; k < i; k ++)
                a[j + k + i] = add(a[j + k + i], (tp == -1 ? mo - a[j + k] : a[j + k]));
}

int main()
{
    re(n), re(m), re(p);
    for(ri i = 1; i <= m; i ++)
        re(lx), re(ly), e[i] = (edge){lx, ly};
    for(ri i = 1; i <= n; i ++)
        re(w[i]);
    int S = 1 << n;
    for(ri s = 0; s < S; s ++)
    {
        int cnt = 0;
        for(ri i = 0; i < n; i ++)
            if((1 << i) & s)
                cnt ++, su[s] += w[i + 1];
        su[s] = ksm(su[s], p), vx[cnt][s] = check(s) ? su[s] : 0;
    }
    dp[0][0] = 1, fwt(dp[0], S, 1);
    for(ri i = 1; i <= n; i ++)
    {
        fwt(vx[i], S, 1);
        for(ri j = 0; j < i; j ++)
            for(ri s = 0; s < S; s ++)
                dp[i][s] = (dp[i][s] + 1ll * dp[j][s] * vx[i - j][s] % mo) % mo;
        fwt(dp[i], S, -1);
        for(ri s = 0; s < S; s ++)
            dp[i][s] = (ask(s) != i) ? 0 : 1ll * dp[i][s] * ksm(su[s], mo - 2) % mo;
        if(i != n)
            fwt(dp[i], S, 1);
    }
    printf("%d", dp[n][S - 1]);
    system("pause");
}

【CF618F】Double Knapsack

这个题目甚是神仙啊QAQ。
假设a数组算到最后总和比b大,我们现在考虑对于每一个i,找出最大的ta满足sa_i>=sb_{ta},其中saa数组的前缀和,sbb数组的前缀和。
这个不等式可以写成0 \leq sa_i – sb_{ta} < n,因为只要大于等于n我们就可以继续向前移动ta
我们从0开始统计这个sa_i – sb_{ta} 的值,那么根据鸽巢原理,一共n+1个数字分配在n个笼子里,至少有两对是相等的,也就说不存在无解的情况。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

typedef unsigned int uint;

template<typename inp_typ>

inline void re(inp_typ &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 1e6 + 10;

int n, lx;

lo sa[ms], sb[ms];

struct in
{
    int x, y;
}pos[ms];

int main()
{
    re(n);
    for(ri i = 1; i <= n; i ++)
        re(sa[i]), sa[i] += sa[i - 1];
    for(ri i = 1; i <= n; i ++)
        re(sb[i]), sb[i] += sb[i - 1];
    for(ri i = 0; i <= n; i ++)
        pos[i] = (in){-1, -1};
    bool f = 0;
    if(sa[n] < sb[n])
        swap(sa, sb), f = 1;
    ri i, ta = 0; lo v;
    for(i = 0; i <= n; i ++)
    {
        while(sa[i] >= sb[ta + 1] && ta + 1 <= n)
            ta ++;
        v = sa[i] - sb[ta];
        //cout << i << ' ' << ta << ' ' << v << '\n';
        if(pos[v].x == -1)
            pos[v] = (in){i, ta};
        else
            break;
    }
    if(f)
        swap(sa, sb), swap(i, ta), swap(pos[v].x, pos[v].y);
    printf("%d\n", i - pos[v].x);
    for(ri j = pos[v].x + 1; j <= i; j ++)
        printf("%d ", j);
    printf("\n");
    printf("%d\n", ta - pos[v].y);
    for(ri j = pos[v].y + 1; j <= ta; j ++)
        printf("%d ", j);
    system("pause");
}

【luoguP2179】[NOI2012]骑行川藏

本来想学拉格朗日乘数法,结果高中数学真香了。
考虑一个t-E函数,E越大,t减小的就越少。
贪心的想,每次要选取t减小最快的来分配能量,但这是实数,没法模拟。
因此我们考虑,每次都这么干,那么最后所有路程的导数会越来越接近,越来越接近,最后完全相等,并且向0靠拢。
所以我们得出的结论是,最后答案对于所有路程来说,导数都是相等的。
因此我们可以二分导数,这个导数一定是个负数,因为随着每段路程E的变大,t减小的越来越慢。
k提前乘上s
\frac{\Delta t}{\Delta E} = \frac{\frac{\Delta t}{\Delta v}}{\frac{\Delta E}{\Delta v}} = \frac{\frac{-s}{v^2}}{2k(v-v’)} = \frac{-s}{2kv^2(v-v’)} = x
其中x是我们二分的导数。
v的求解同样可以二分,时间复杂度O(nlog^2n)

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

typedef long double ld;

template<typename inp_typ>

inline void re(inp_typ &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const int ms = 1e4 + 10;

const double inf = 1e15;

int n;

double Eu, s[ms], k[ms], v[ms];

inline double ask(int pos, double x)
{
    double l = max(v[pos], 0.0), r = 1e5 + 10, mid; int cnt = 60;
    while(cnt --)
    {
        mid = (l + r) / 2;
        //tmp = (-s[pos]) / (2 * k[pos] * mid * mid * (mid - v[pos]));
        if(2 * k[pos] * mid * mid * (mid - v[pos]) * x > -s[pos])
            l = mid;
        else
            r = mid;
    }
    return (l + r) / 2;
}

inline double check(double x)
{
    double S = 0;
    for(ri i = 1; i <= n; i ++)
    {
        double V = ask(i, x);
        S += k[i] * (V - v[i]) * (V - v[i]);
    }
    return S;
}

int main()
{
    re(n); scanf("%lf", &Eu);
    for(ri i = 1; i <= n; i ++)
        scanf("%lf%lf%lf", &s[i], &k[i], &v[i]), k[i] *= s[i];
    double l = - inf, r = 0, mid; int cnt = 100;
    while(cnt --)
    {
        mid = (l + r) / 2;
        if(check(mid) <= Eu)
            l = mid;
        else
            r = mid;
    }
    mid = (l + r) / 2;
    double ans = 0;
    for(ri i = 1; i <= n; i ++)
    {
        double V = ask(i, mid);
        ans += s[i] / V;
    }
    printf("%.6lf", ans);
}

【BZOJ4487】[JSOI2015]染色问题

这算是个容斥的模板题目,只要对容斥理解的足够好就可以一眼秒掉。
也不用强行固定行/列合法,直接考虑3维状态c_{i,j,k}表示至少i行,j列,k种颜色不合法,那么考虑下每次都是偶数次+奇数次-
那么答案就很明显了
\sum_{i=0}^n\sum_{j=0}^m\sum_{k=0}^C (-1)^{i+j+k}C_{n}^{i} C_{m}^j C_{C}^k (C-k+1)^{(n-i)(m-j)}
网上有人写的k^{(n-i)(m-j)}……那别写成k种颜色不取啊,虽然最后算出来的式子确实一个事情。
之所以+1,是因为不涂本身也要算成一种颜色。

#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

template<typename inp_typ>
inline void re(inp_typ &x)
{
    x = 0;
    char a; 
    while(!isdigit(a = getchar())) ;
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
}

int n, m, c;

lo fac[2020], inv[2020];

const lo mo = 1e9 + 7;

inline lo ksm(lo x, lo k)
{
    lo a = x, rt = 1;
    while(k)
        rt = rt * ((k & 1) ? a : 1) % mo, a = a * a % mo, k >>= 1;
    return rt;
}

lo ans;

int main()
{
    fac[0] = 1, inv[0] = 1, fac[1] = 1, inv[1] = 1;
    for(ri i = 2; i <= 2000; i ++)
        fac[i] = fac[i - 1] * i % mo;
    inv[2000] = ksm(fac[2000], mo - 2);
    for(ri i = 1999; i >= 2; i --)
        inv[i] = inv[i + 1] * (i + 1) % mo;
    re(n), re(m), re(c);
    for(ri i = 0; i <= n; i ++)
        for(ri j = 0; j <= m; j ++)
            for(ri k = 0; k <= c; k ++)
            {
                lo tmpa = fac[n] * inv[n - i] % mo * inv[i] % mo;
                lo tmpb = fac[m] * inv[m - j] % mo * inv[j] % mo;
                lo tmpc = fac[c] * inv[c - k] % mo * inv[k] % mo;
                lo Tmp = tmpa % mo * tmpb % mo * tmpc % mo * ksm(c - k + 1, (n - i) * (m - j) % (mo - 1)) % mo;
                if((i + j + k) & 1)
                    ans -= Tmp, ans += (ans < 0) ? mo : 0;
                else
                    ans += Tmp, ans -= (ans >= mo) ? mo : 0;
            }
    printf("%lld", ans);
    system("pause");
}

【CF785D】Anton and School – 2

这个题是伟大的红太阳学长出给我和刘神仙做的题,当时考场只想到了60分奇怪dp,考完听学长一讲才恍然大悟
首先考虑最暴力的dp
\(\sum_{i=1}^{n}\sum_{j=1}^{min(a_i-1, b_i-1)}C_{a_i}^{j}C_{b_i-1}^{j}\)
ai是表示目前左括号个数,bi右括号,这个显然n^2,过不掉
那么,我们是不是可以化简这个式子呢
\(\sum_{j=1}^{min(a_i-1, b_i-1)}C_{a_i}^{j}C_{b_i-1}^{j}=\sum_{j=1}^{min(a_i-1, b_i-1)}C_{a_i}^{a_i-j}C_{b_i-1}^{j}\)
这个式子开始变得和原来的式子不一样了,我们开始从这个式子非公式角度的去讨论它,这个式子就表示,在ai种物品里面选取ai-j种,在bi-1种物品里选择j种(我们保证i这位一定被选择)
那么这俩式子一乘,再求个和,实际上就等于\(C_{a_i+b_i-1}^{a_i}\)
这个式子就表示在ai+bi-1种物品里面选择ai个物品的方案数
那么我现在就可以得到这个式子\(\sum_{i=1}^{n}C_{a_i+b_i-1}^{a_i}\),这个东西显然可以递推,时间复杂度O(n)(线性求逆元的时候)

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register long long

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = (x << 1) + (x << 3) + a - '0', a = getchar();
    if(b == 1)
        x *= -1;
}

const int ms = 200010;

const lo mo = 1e9 + 7;

int n, a[ms], b[ms];

bool fl[ms];

lo ans, inv[ms], pre[ms];

char lx;

int main()
{
    while(((lx = getchar()) != '(' && lx != ')')); inv[0] = inv[1] = pre[1] = pre[0] = 1;
    while(lx == '(' || lx == ')')
        fl[++ n] = (lx == '(') ? 0 : 1, a[n] = a[n - 1] + (fl[n] == 0), lx = getchar();
    for(ri i = n; i >= 1; i --)
        b[i] = b[i + 1] + (fl[i] == 1);
    for(ri i = 2; i <= n; i ++)
        inv[i] = inv[i - 1] * i % mo, pre[i] = (mo - mo / i) * pre[mo % i] % mo;
    for(ri i = 1; i <= n; i ++)
        pre[i] = pre[i] * pre[i - 1] % mo;
    for(ri i = 1; i <= n; i ++)
    {
        if(fl[i] == 1)
            continue;
        ans = (ans + inv[a[i] + b[i] - 1] * pre[a[i]] % mo * pre[b[i] - 1] % mo) % mo;
    }
    printf("%lld\n", ans); 
} 

【洛谷P1447】能量采集

这个题开始我还想用些奇奇怪怪的方法水过去,然后失败了,看了题解发现是一道莫比乌斯反演的题目,以后会用latex以后再填上具体推论过程这个坑吧qwq
这个题我们先这么想,假如横纵坐标互质,那么它一定是一个直线上经过的第一个非原点的点,那么横纵坐标各2,3……那么我们就可以得出,一个点对答案的贡献是(gcd(x,y)-1)*2+1
那么也就是说,枚举xy,然后就能计算答案了,但是这样是n^2的,那么我们换个思路求答案,因为枚举gcd是o(n)的,那么我们可以设g[i]表示有g[i]个最大公因数为i,但是我们没法直接求g[i],所以再引入一个函数f[i]表示有f[i]个数公因数为i,那么g[i] = f[i] – f[2 * i] – f[3 * i] – …… – f[k * i](k * i <= min(n, m))(这里其实是莫比乌斯反演的思想)
那么我们根据这个思路做就好,时间复杂度大概在nlogn左右qwq,菜鸡不会证明

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector> 
#include<cmath>
#include<stack>
#include<queue>
#include<map>
#define ri register int

using namespace std;

typedef long long lo;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && ((t = (h = buf) + fread(buf, 1, 100000, stdin), t == h)) ? EOF : *h ++;
}

inline void re(lo &x)
{
    x = 0;
    char a = getchar(); bool b = 0;
    while(a < '0' || a > '9')
    {
        if(a == '-')
            b = 1;
        a = getchar();
    }
    while(a >= '0' && a <= '9')
        x = (x << 3) + (x << 1) + a - '0', a = getchar();
    if(b == 1)
        x *= -1;
}

lo n, m, mi, dp[100010], ans;

int main()
{
    re(n), re(m);
    mi = (n > m) ? m : n;
    for(ri i = mi; i >= 1; i --)
    {
        dp[i] = (n / i) * (m / i);
        for(ri j = 2; j * i <= mi; j ++)
            dp[i] -= dp[j * i];
        ans += (i + i - 1) * dp[i];
    }
    printf("%lld", ans);
}