【codevs2382】挂缀

这个题……服气了
我们假设之前已经选择了\(w\)重量的珠子,现在我们要考虑a挂b上比较优还是b挂a上比较优
b挂a上的时候,\(c_{a} \geq w_{b} + w, c_{b} \geq w\)
a挂b上的时候,\(c_{b} \geq w_{a} + w, c_{a} \geq w\)
所以如果a挂b上比较优的话\(c_{b} – (w_{a} + w) \geq c_{a} – (w_{b} + w)\),既\(c_{b} + w_{b} \geq c_{a} + w_{a}\)
反之\(c_{b} – (w_{a} + w) \leq c_{a} – (w_{b} + w)\),既\(c_{a} + w_{a} \geq c_{b} + w_{b}\)
我们要留尽可能多的承重力挂别的珠缀,这样我们降序排序即可,但是并不好处理。所以我们正着排,如果\(c_{a} \geq w\),就直接往上挂,否则从里面调出一个最重的踢出去就行了

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#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), h == t) ? EOF : *h ++;
}

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;
}

lo n, w, lx, ly, ans;

struct in
{
    lo c, w, s;
}ter[200020];

inline bool cmp(in a, in b)
{
    return a.s < b.s;
}

priority_queue <lo> qwq;

int main()
{
    re(n);
    for(ri i = 1; i <= n; i ++)
        re(lx), re(ly), ter[i] = (in){lx, ly, lx + ly};
    sort(ter + 1, ter + 1 + n, cmp);
    for(ri i = 1; i <= n; i ++)
    {
        if(w <= ter[i].c)
            w += ter[i].w, ans ++, qwq.push(ter[i].w);
        else
        {
            lo qaq = qwq.top();
            if(qaq > ter[i].w)
                w += ter[i].w - qaq, qwq.pop(), qwq.push(ter[i].w); 
        }
    }
    printf("%lld\n%lld", (lo)qwq.size(), w);
}

【算法】博弈论

已经看了好几次博弈论了,前几次没记最后都忘了,所以这次试着记一下,以后忘了还可以顺着记忆找回来
日常安利 [学习笔记] (博弈论)Nim游戏和SG函数
博弈论一般都是从nim游戏开始的,这是博弈论中最为经典的问题之一。一般都是给你n堆石子,两个人轮流去拿一堆里面的石子,最少1个最多全拿走,然后问你先手必胜还是必败
这个东西是有结论的,我们可以把每一堆作为一个子游戏去考虑的话,分别求出他们的sg函数,之后求一个异或和,如果异或和为0必败,异或和不为0必胜
为什么?我们这么考虑,假设有n堆石子,现在轮到后手操作,之前先手把异或和变为了非0,既异或和\(x \neq 0\),那么一定存在一堆石子\(a_{i}\)的,他的最高位和\(x\)最高位都为1,那么我们可以让这堆石子变小,变成\(a_{i} xor x\)(\(a_{i} xor x\)一定小于\(a_{i}\)的),那么我们既消掉了最高位,又消掉了后面那些1,所以异或和又变为了0。因此无论怎么改变对于先手异或和都为0,这个过程肯定不是无限的,所以最后到先手手上的时候一定必败
那么sg函数是什么
sg函数就是说给你一些数,其中最小的没有出现的非负整数即为sg函数
那么对于一个空集,\(sg(x) = 0\)
因此对于\(sg(x) \neq 0\)的情况来说,在他的集合里面一定存在一个数为0;反之亦然
这和博弈论有什么关系
引入接下来两个定义
P-position:在当前的局面下,先手必败
N-position:在当前的局面下,先手必胜
那么我们将nim游戏看成一张图,对于每次转移都建边,sg函数的集合就是他能到达的点的sg值。对于一个必胜态,一定sg值不为0,否则为0
那么结合上面的来看我们可以通过在这个图上移动实现必胜态必败态之间的转换
这就是sg值和博弈论的关系
那么sg值怎么求?
对于从1-m的转移,\(sg(x)=x%(m+1\))
对于全部都能取的情况,\(sg(x)=x\)
对于不连续的转移,我们需要背模板
先写一个第二种情况的(其实与第一种情况是一样的)
luogu P2197 nim游戏

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#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), h == t) ? EOF : *h ++;
}

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;
}

int t, n, lx;

int main()
{
    re(t);
    while(t --)
    {
        re(n), lx = 0;
        for(ri i = 1, j; i <= n; i ++)
            re(j), lx ^= j;
        if(lx > 0)
            printf("Yes\n");
        else
            printf("No\n");
    }
}

除了nim游戏还有一些模型,比如二分图博弈
二分图博弈的思想就是先将博弈转化成二分图最大匹配,这个时候如果二分图完美匹配的话,先手必胜,否则先手就可以通过选择匹配点获得胜利
难就难在所有可能匹配点的都是答案,我习惯写dinic来判断二分图最大匹配,这个时候怎么做?
从源点出发找出所有源点能到达的,并且本来与源点也相连的点,汇点也这么干一次(目前不理解,就先这么咕咕咕)
luogu P4055 [JSOI2009] 游戏

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#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), h == t) ? EOF : *h ++;
}

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;
}

int n, m, t, tot = -1, cnt, head[10010], he[10010], pos[110][110], px[10010], py[10010];

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}, de[10010], q[10010];

int ax[10010], ay[10010];

char lx;

bool mmp[110][110], flag[10010], col[10010];

struct in
{
    int to, ne, co;
}ter[100010];

inline void build(int f, int l, int c)
{
    ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
    ter[++ tot] = (in){f, head[l], 0}, head[l] = tot;
}

inline bool bfs()
{
    int hh = 0, tt = 0;
    q[0] = 0, memset(de, 0, sizeof(de)), de[0] = 1;
    while(hh <= tt)
    {
        int qaq = q[hh ++];
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(ter[i].co > 0 && de[to] == 0)
                q[++ tt] = to, de[to] = de[qaq] + 1;
        }
    }
    return de[t] > 0;
}

int dfs(int no, int fl)
{
    if(no == t)
        return fl;
    for(ri &i = he[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(ter[i].co > 0 && de[to] == de[no] + 1)
        {
            int rt = dfs(to, min(fl, ter[i].co));
            if(rt > 0)
            {
                ter[i].co -= rt, ter[i ^ 1].co += rt; return rt;
            }
        }
    }
    return 0;
}

void dfss(int no, int f)
{
    flag[no] = 1;
    if(col[no] == f)
        ax[++ cnt] = no;
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(ter[i].co == f && flag[to] == 0)
            dfss(to, f);
    }
}

int main()
{
    re(n), re(m), memset(head, -1, sizeof(head));
    for(ri i = 1; i <= n; i ++)
    {
        while((lx = getchar()) != '#' && lx != '.');
        for(ri j = 1; j <= m; j ++)
        {
            mmp[i][j] = (lx == '.');
            if(mmp[i][j] > 0)
                pos[i][j] = ++ cnt, px[cnt] = i, py[cnt] = j;
            lx = getchar();
        }
    }
    t = ++ cnt;
    for(ri i = 1; i <= n; i ++)
        for(ri j = 1; j <= m; j ++)
            if(mmp[i][j] == 1)
            {
                if((i + j) & 1)
                {
                    build(0, pos[i][j], 1), col[pos[i][j]] = 1;
                    for(ri k = 0; k < 4; k ++)
                    {
                        int tx = i + dx[k], ty = j + dy[k];
                        if(tx < 1 || tx > n || ty < 1 || ty > m || mmp[tx][ty] == 0)
                            continue;
                        build(pos[i][j], pos[tx][ty], 1);
                    }
                }
                else
                    build(pos[i][j], t, 1);
            }
    int nu = 0, x = 0;
    while(bfs())
    {
        memcpy(he, head, sizeof(he));
        while(x = dfs(0, 1000000007))
            nu += x;
    }
    if((nu << 1) == cnt - 1)
    {
        printf("LOSE"); return 0;
    }
    printf("WIN\n");
    cnt = 0, col[t] = 1;
    dfss(0, 1), memset(flag, 0, sizeof(flag)), dfss(t, 0);
    sort(ax + 1, ax + 1 + cnt);
    for(ri i = 1; i <= cnt; i ++)
        if(ax[i] != 0 && ax[i] != t)
            printf("%d %d\n", px[ax[i]], py[ax[i]]);
}

博弈论还可以打表,luogu P2148 [SDOI2009]E&D
这个题目首先你可以暴力去算,对于a+b来说,他一定能够化成c+d的形式,我们按照按照a来算,然后每次枚举被拆成了哪两个数,异或起来,然后这样得到了sg值集合。我们发现,a+b异或起来之后的答案,就是从最低位开始数第一个0出现在第几位上?所以我们可以logn去算?完了?
整个题目就是通过打表找规律实现的?蛇皮操作啊

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#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), h == t) ? EOF : *h ++;
}

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;
}

int t, n, lx, ly, ans;

inline int mex(int x)
{
    int rt = 0;
    while(x & 1)
        x >>= 1, rt ++;
    return rt;
}

int main()
{
    re(t);
    while(t --)
    {
        re(n), ans = 0;
        for(ri i = 1; i <= n; i += 2)
            re(lx), re(ly), ans ^= mex((lx - 1) | (ly - 1));
        printf("%s\n", ans ? "YES" : "NO");
    }
}

博弈论还可以脑洞清奇一点,不使用sg函数。luogu P4101 [HEOI2014] 人人尽说江南好
这个题目脑洞实在是太过于清奇了,清奇的妙不可言
首先可以这么考虑,合并次数为奇数先手必胜,偶数后手必胜,那么两个人都会尽可能向着自己想要的方向去发展,结果就是……这两个人把比赛拉到最长(感性理解下)
之后我们要考虑,如果最长的合并次数是偶数次,那么一定后手能必胜
分开讨论下,当\(n \leq m\)时,这种情况最后肯定能合成一堆qwq,我们管这个比较大的堆叫【大堆】,假如说现在轮到先手操作,先手还没动,这个时候最长合并次数为偶数次,那么先手有两种可能性,把后面一个堆丢进大堆里面,这样后手再丢一个小堆进去,或者把后面两个堆合成一个,那么后手就可以把这个合成的直接丢进去。无论怎么做,后手都能保证每轮完了之后,大堆的石子会增加两个,那么合并次数也会-2,一直保持为偶数。直到最后先手合无可合。
那么\(n > m\)呢?我们假设\(n = m + 1\),并且m是奇数,最后合成次数最多的情况一定是\((m, 1)\)对于前m个,合成次数为偶数,我们就像刚才那么操作,最后一个1直接不用管。所以后手必赢。同样的我们可以把情况扩展到\(n = km + b\)这种情况。前k个\(m\)一样合并,后面也一样。
所以我们只需要算出合并次数就可以了
[BZOJ3609]-[Heoi2014]人人尽说江南好-神分析+博弈 dalao写的好qwq

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#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), h == t) ? EOF : *h ++;
}

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;
}

int t, n, m;

int main()
{
    re(t);
    while(t --)
    {
        re(n), re(m);
        lo x = (n / m) * (m - 1) + (n % m ? n % m - 1 : 0);
        printf("%d\n", (x & 1) ? 0 : 1);
    }
}

【算法】欧拉路&欧拉回路

欧拉路和欧拉回路是数学家欧拉在研究七桥问题的时候提出的,其具体历史这里就不多说了。
简单区分下欧拉回路和欧拉路
欧拉路就是说所有的边走且只走一次,欧拉回路就是在欧拉路的基础上更进一层,不仅所有的边都走一次,最后还回到了起点
其实就是我们熟知的一笔画呗
这个算法其实比较结论。对于有向图和无向图我们只需要找准条件随便写一下就行了,混合图……反正我是没看懂23333333
有向图存在欧拉路:所有顶点出度等于入度(且存在欧拉回路);或者是出两点外,所有点出度等于入度,这两个点中,出度大的为起点,入度大的为终点。
无向图存在欧拉路:所有点度数均为偶数(且存在欧拉回路);或有两个奇数点,他们一定是终点和起点
代码实现的话直接dfs就好啦。反正是一笔画,所以只要能走就一直走就行,记住dfs的时候要修改边权
luogu P1341 无序字母对

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#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), h == t) ? EOF : *h ++;
}

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;
}

int n, dis[1010][1010], d[1010];

char s[1010], ans[1010], ss[1010];

void dfs(int no)
{
    for(ri i = 0; i < 52; i ++)
        if(dis[no][i])
            dis[no][i] = dis[i][no] = 0, dfs(i);
    ans[n --] = ss[no];
}

int main()
{
    re(n);
    for(ri i = 0; i < 26; i ++)
        ss[i] = 'A' + i;
    for(ri i = 26; i < 52; i ++)
        ss[i] = 'a' + i - 26;
    for(ri i = 1; i <= n; i ++)
    {
        scanf("%s", s + 1);
        int lx, ly;
        if(s[1] >= 'A' && s[1] <= 'Z')
            lx = s[1] - 'A';
        else
            lx = s[1] - 'a' + 26;
        if(s[2] >= 'A' && s[2] <= 'Z')
            ly = s[2] - 'A';
        else
            ly = s[2] - 'a' + 26;
        dis[lx][ly] = dis[ly][lx] = 1, d[lx] ++, d[ly] ++;
    }
    int num = 0, sta = -1;
    for(ri i = 0; i < 52; i ++)
        if(d[i] & 1)
        {
            num ++;
            sta = (sta == -1) ? i : sta;
        }   
    bool f = 0;
    if((num != 0 && num != 2) || f != 0)
    {
        printf("No Solution"); return 0;
    }
    if(sta == -1)
    {
        for(ri i = 0; i < 52; i ++)
            if(d[i] != 0)
            {
                sta = i; break;
            }
    }
    dfs(sta);
    if(n > 0)
    {
        printf("No Solution"); return 0;
    }
    printf("%s", ans);
}

【luoguP4370】[Code+#4]组合数问题2

暑假数学班的题目能让我咕咕咕到现在也是可以的,现在列表里面一堆模板还没做,noip前应该也不会做了2333333
这个题目是当时长者给我们讲的,脑洞真是清奇2333333333
首先分析这个题目的话,难点就在于,我们取模以后没法判断数字的大小了。这个时候有一个比较显然的思路,用double类型去存储组合数。但是组合数太大了,double类型只能存20位左右的精准数字,剩下的全部以浮点数的形式存储,那么怎么比较大小呢?
这也就是这个题目的关键,我们利用对数函数来判断数字的大小。我们统一取log2函数值的大小,这样就可以保证精度的同时判断大小了2333333
代码实现并不难,就是有点小恶心,开始wa了发,后来看到网上dalao的偷懒写法写了一发

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#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), h == t) ? EOF : *h ++;
}

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 ms = 1e6 + 10;

const lo mo = 1e9 + 7;

lo n, k, ans, fac[ms], inv[ms], fx[4] = {-1, 0, 1, 0}, fy[4] = {0, 1, 0, -1};

double fc[ms];

struct in
{
    lo x, y, c; double lg;
    inline in(lo a, lo b)
    {
        x = a, y = b, lg = fc[a] - fc[b] - fc[a - b];
        c = fac[a] * inv[b] % mo * inv[a - b] % mo;
    }
    inline bool operator < (const in &a) const
    {
        return lg < a.lg;
    }
};

priority_queue <in> qwq;

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

int main()
{
    re(n), re(k), fac[0] = inv[0] = 1;
    for(ri i = 1; i <= n; i ++)
        fac[i] = (fac[i - 1] * i) % mo, fc[i] = fc[i - 1] + log2(i);
    inv[n] = ksm(fac[n], mo - 2);
    for(ri i = n - 1; i > 0; i --)
        inv[i] = inv[i + 1] * (i + 1) % mo;
    for(ri i = 0; i <= n; i ++)
        qwq.push(in(n, i));
    while(k --)
    {
        in qaq = qwq.top(); qwq.pop();
        ans = (ans + qaq.c) % mo, qaq.x --;
        qwq.push(in(qaq.x, qaq.y));
    }
    printf("%lld", ans);
}

【luoguP4364】 [九省联考2018]IIIDX

这个题目当初我考场就是个智障,连55的贪心都没做对qwq
首先一个比较显然的思路,我们先建树,\(\lfloor{\frac{i}{k}}\rfloor\)即为\(i\)的父亲,然后我们从大到小排个序,按照中序遍历给他赋值
但是这样的贪心在\(d_{i}\)重复的时候就gg了,因为我们发现可以用子树内部较大的值去换掉其他子树上比较小的值,因此我们要换个思路贪心
我们还是排序,每次去寻找一个可以容纳的下子树大小的区间,比如9 9 9 8 7 7 6 6 6 5,这个时候我们要插入一棵大小为7的子树。这个时候我们很显然会找到第7个数——6。然后我们再一直移动到第九个数——还是6。这是为了保证和我同一层的子树根尽可能的大,所以在我这棵子树的根并不会变小的时候,我多留点空为后面的子树。
这个时候我们为了防止别的树占用我们的预定好了的区间,所以我们需要设置一个辅助数组。设mi[i]表示权值大于等于i的数还有多少是可以选择的,那么排序过后mi[i]就可以转化为i左边还剩下多少数字可以使用。这个东西显然是满足单调不降的。那么我们就可以线段树去维护,每次预定的时候就区间减法
然而大多数人都选择了将减法变为加法,将被选取的区间和整个一段取了个补集,让他们进行区间加。这也就是为什么网上这么多题解嘴上都在说减法实际上一个减法都没有的原因。
每次变更父亲的时候提前钦定一波,每个子树选完了就再减回去。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#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 ++;
}

inline void re(int &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 = 5e5 + 10;

int n, a[ms], fa[ms], sz[ms], cnt[ms], pos[ms];

struct in
{
    int l, r, mi, add;
}ter[ms << 2];

double k;

inline bool cmp(int a, int b)
{
    return a > b;
}

inline void up(int w)
{
    ter[w].mi = min(ter[w << 1].mi, ter[w << 1 | 1].mi);
}

inline void build(int w, int l, int r)
{
    ter[w] = (in){l, r, l};
    if(l == r)
        return;
    int mid = (l + r) >> 1;
    build(w << 1, l, mid), build(w << 1 | 1, mid + 1, r);
}

inline void down(int w)
{
    int &add = ter[w].add;
    ter[w << 1].add += add, ter[w << 1 | 1].add += add;
    ter[w << 1].mi += add, ter[w << 1 | 1].mi += add;
    add = 0;
}

void change(int w, int l, int r, int v)
{
    if(ter[w].l == l && ter[w].r == r)
    {
        ter[w].mi += v, ter[w].add += v; return;
    }
    int mid = (ter[w].l + ter[w].r) >> 1; down(w);
    if(r <= mid)
        change(w << 1, l, r, v);
    else if(l > mid)
        change(w << 1 | 1, l, r, v);
    else
        change(w << 1, l, mid, v), change(w << 1 | 1, mid + 1, r, v);
    up(w);
}

int ask(int w, int l)
{
    if(ter[w].l == ter[w].r)
        return ter[w].mi >= l ? ter[w].l : ter[w].l + 1;
    int mid = (ter[w].l + ter[w].r) >> 1; down(w);
    if(ter[w << 1 | 1].mi >= l)
        return ask(w << 1, l);
    return ask(w << 1 | 1, l);
}

int main()
{
    re(n), scanf("%lf", &k);
    for(ri i = 1; i <= n; fa[i] = (int)i / k, sz[i] = 1, re(a[i ++]));
    sort(a + 1, a + 1 + n, cmp);
    for(ri i = n; i >= 1; i --)
        sz[fa[i]] += sz[i];
    for(ri i = n - 1; i >= 0; i --)
        cnt[i] = (a[i] == a[i + 1]) ? cnt[i + 1] + 1 : 0;
    build(1, 1, n);
    for(ri i = 1; i <= n; i ++)
    {
        if(fa[i] && fa[i - 1] != fa[i])
            change(1, pos[fa[i]], n, sz[fa[i]] - 1);
        int x = ask(1, sz[i]);  x += cnt[x], cnt[x] ++, x -= (cnt[x] - 1);
        change(1, x, n, - sz[i]), pos[i] = x;
    }
    for(ri i = 1; i <= n; printf("%d ", a[pos[i ++]]));
}

【luoguP3746】组合数问题

这个题目……开始我yy了一个dp方程为\(dp[i] = dp[i – 1] + C_{nk}^{ik + r}\),然后矩阵一波发现emmmmmm里面有个组合数是会随着i的增长,m不断改变的。然后我就弃疗了。看完题解以后顿时觉得自己是个zz啊
组合数的递推公式\(C_{n}^{m}=C_{n-1}^{m-1}+C_{n-1}^{m}\),那么我这个式子加个\(\\sum\)也不是不行啊
于是式子变成了这样\(\sum C_{n}^{m} = \sum C_{n – 1}^{m – 1} + \sum C_{n – 1}^{m}\)
然后我就可以设置dp[i][j] = dp[i-1][j-1] + dp[i-1][j],dp[i][j]表示$n$为i的时候且m为$a*k+j$的时候的答案
这个东西显然可以矩阵快速幂优化
但是其实这个方程这么写是错的
$j$为$0$的时候$j-1$不就是$-1$了吗
那么真正的方程式为dp[i][j] = dp[i – 1][j] + dp[i – 1][(j – 1 + k) % k]

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#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), 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 * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

lo n, p, k, r;

struct in
{
    lo a[55][55];
}a, ans;

in operator * (in x, in y)
{
    in c; memset(c.a, 0, sizeof(c.a));
    for(ri kk = 0; kk < k; kk ++)
        for(ri i = 0; i < k; i ++)
            for(ri j = 0; j < k; j ++)
                c.a[i][j] = (c.a[i][j] + x.a[i][kk] * y.a[kk][j] % p) % p;
    return c;
}

int main()
{
    re(n), re(p), re(k), re(r), n *= k;
    for(ri i = 0; i < k; i ++)
        a.a[i][i] ++, a.a[(i - 1 + k) % k][i] ++;
    for(ri i = 0; i < k; i ++)
        ans.a[i][i] = 1;
    while(n)
    {
        if(n & 1)
            ans = a * ans;
        a = a * a, n >>= 1;
    }
    printf("%lld", ans.a[0][r]);
}

【洛谷P4882】lty loves 96!

开始的时候看到这个题目有点懵逼,因为没仔细看条件,以为有几个条件是保证对于每一个abc
我们考虑,对于一个数字,只有最后两个加进去的才是有意义的,之前怎么摆最后只需要保留已经满不满足第三个大条件即可。所以我们可以设一个裸的状态dp[i][j][x][y][0/1]表示当前已经放了i位数,有j个9/6,第i位为y,i-1位为x,是否满足第三个条件的方案数。那么转移方程也比较显然了,这里就不再写转移方程,具体分析下情况。我们每次转移的时候枚举最后三位数。如果后三位数能满足条件,则能从非法转移到合法,否则只能从非法转移到非法。原本合法的一定转移过来。
注意,这个题目是认为倒数第三位为模数c的qwq

// luogu-judger-enable-o2
#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#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), h == t) ? EOF : *h ++;
}

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;
}

const int mo = 1e8;

int n, m, t;

struct in
{
    int a[55];
    void init(int x)
    {
        memset(a, 0, sizeof(a)), a[a[0] = 1] = x;
    }
}dp[2][51][10][10][2];

in operator + (in a, in b)
{
    int d = max(a.a[0], b.a[0]);
    for(ri i = 1; i <= d; i ++)
        a.a[i] += b.a[i], a.a[i + 1] += a.a[i] / mo, a.a[i] %= mo;
    while(a.a[d + 1] > 0)
        d ++, a.a[d + 1] += a.a[d] / mo, a.a[d] %= mo;
    a.a[0] = d; return a;
}

inline void print(in a)
{
    int mx = a.a[0]; printf("%d", a.a[mx]);
    for(ri i = mx - 1; i >= 1; i --)
        printf("%08d", a.a[i]);
    printf("\n");
}

inline bool check(int x)
{
    return x == 9 || x == 6;
}

int main()
{
    //freopen("data.txt", "r", stdin);
    //freopen("qwq.out", "w", stdout);
    re(n), re(m);
    if(n == 1)
    {
        printf(m == 0 ? "9" : "2"); return 0;
    }
    else if(n == 2)
    {
        printf(m == 0 ? "90" : (m == 1 ? "34" : "4")); return 0;
    }
    for(ri i = 0; i < 10; i ++)
        for(ri j = 0; j < 10; j ++)
            dp[t][check(i) + check(j)][i][j][0].init(1);
    for(ri i = 3; i <= n; i ++)
    {
        t ^= 1;
        for(ri j = 0; j < i; j ++)
            for(ri x = 0; x < 10; x ++)
                for(ri y = 0; y < 10; y ++)
                    dp[t][j][x][y][0].init(0), dp[t][j][x][y][1].init(0); 
        for(ri j = 0; j < i; j ++)
            for(ri x = 0; x < 10; x ++)
                for(ri y = 0; y < 10; y ++)
                    for(ri z = 0; z < 10; z ++)
                    {
                        dp[t][check(z) + j][z][y][1] = dp[t][check(z) + j][z][y][1] + dp[t ^ 1][j][y][x][1];
                        if(check(x + y + z)
                        || (x && check((y * y + z * z) % x)))
                            dp[t][check(z) + j][z][y][1] = dp[t][check(z) + j][z][y][1] + dp[t ^ 1][j][y][x][0];
                        else
                            dp[t][check(z) + j][z][y][0] = dp[t][check(z) + j][z][y][0] + dp[t ^ 1][j][y][x][0];
                    }
    }
    in ans; ans.init(0);
    for(ri i = 1; i < 10; i ++)
        for(ri j = 0; j < 10; j ++)
            for(ri k = m; k <= n; k ++)
                ans = ans + dp[t][k][i][j][1];
    print(ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

【洛谷P3266】[JLOI2015]骗我呢

更正题面,对于\(1 \le i \le n\); \(1 \le j <m\) 满足 \(x_{i,j} < x_{i,j+1}\)
对于每一行,一共有m个数,值域为\([0, m]\),而且每行的数单调上升,很显然,\([0, m]\),这些只有一个数不出现。并且我们每次新加一行的时候,只需要考虑上一行的状态就行了,因此我们列出一个朴素的dp状态,设dp[i][j]表示当前已经放了i行,最后一行缺的是j,转移方程为\(dp_{i,j} = \sum_{k = min(0, j + 1)}^{j + 1}dp_{i – 1, k}\),这个东西我们可以算一下就知道了,当m = 4,的时候,目前为0134,上一行为0124,这样是合法的,但是上一行为0123的时候这样就不合法了
那么现在我们将方程式变一下形,\(dp_{i, j} = dp_{i, j – 1} + dp_{i – 1, j + 1}\),可以发现现在我们每次转移只会向右一格&向左下一格。在这里题目的美妙即将展开了。我们现在可以把式子转化成图。
就是这么一张图片,问你从平行四边形右下走到左上且不跨越A B两直线的方案数。这样我们有一个比较显然的思路,用总方案数减去不合法的方案数。那么我们用A表示这个方案跨越了左边的边界,用B表示这个方案跨越了右边的边界。我们设最左下角的为\((0, 0)\),左侧直线表达式为\(y_{A} = x + 1\),右侧表达式为\(y_{B} = x – (m + 2)\)
那么我们的目的是去除形如ABABBBBAAAABABABAAAB这些方案。对于刚才那个方案,我们发现连续的一段区间可以直接缩成一个字母——他一直在跨越同一个边界,没有意义。所以刚才那个可以缩水成ABABABABABAB这样的方案。接下来,我们令初始点为\((n+m+1,n)\),重复以下操作:
将当前点以直线A为对称轴翻转,然后将原点到当前点的方案数从答案中减去,再将当前点以直线B为对称轴翻转,把原点到当前点的方案给加上,一直重【复】复【读】,直到当前点的任意一维坐标小于0结束。
这样子我们就相当于将以A和AB为后缀的方案删除了,然后把BA和BAB为后缀的方案加回去……所以实际上我们到最后是把以A为前缀的方案删除了。
同理再对B做一遍这样的操作。总方案为//(C_{2 * n + m + 1}^{n})。
放代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#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), h == t) ? EOF : *h ++;
}

const lo mo = 1e9 + 7;

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;
}

lo n, m, d, ans, inv[3000010], fac[3000010];

lo c(lo x, lo y)
{
    if(x < y)
        return 0;
    return fac[x] * inv[y] % mo * inv[x - y] % mo;
}

lo cc(lo x, lo y)
{
    if(x < 0 || y < 0)
        return 0;
    return c(x + y, y);
}

inline void change(lo &x, lo &y, lo num)
{
    swap(x, y), x += num, y -= num;
}

inline lo 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 rt;
}

int main()
{
    re(n), re(m), d = max(n, m), inv[1] = inv[0] = fac[1] = fac[0] = 1;
    for(ri i = 2; i <= 3000000; i ++)
        fac[i] = fac[i - 1] * i % mo;
    inv[3000000] = ksm(fac[3000000], mo - 2);
    for(ri i = 2999999; i >= 2; i --)
        inv[i] = inv[i + 1] * (i + 1) % mo;
    lo lx = n + m + 1, ly = n;
    ans = cc(lx, ly);
    while(lx >= 0 && ly >= 0)
        change(lx, ly, -1), ans -= cc(lx, ly), change(lx, ly, m + 2), ans += cc(lx, ly), ans %= mo;
    lx = n + m + 1, ly = n;
    while(lx >= 0 && ly >= 0)
        change(lx, ly, m + 2), ans -= cc(lx, ly), change(lx, ly, -1), ans += cc(lx, ly), ans %= mo;
    ans = (ans % mo + mo) % mo, printf("%lld", ans);
    return 0;
}

【NOI OpenJudge 7627】鸡蛋的硬度

这个题时隔一年多以后我看这个题目还是一脸懵逼,看完题解后恍然大悟。我们设dp[i][j]表示当前有i个楼层,用了j个鸡蛋最坏需要丢多少次,那么转移我们可以通过分解成子问题来做。dp[i][j] = min(dp[i][j], max(dp[k – 1][j – 1], dp[i – k][j]) + 1)。这个max什么意思呢?

这个图蓝色的部分就是第k层红色的部分就是dp[i – k][j],即表示我们在k这一层没有把鸡蛋摔碎,楼上那些需要几次确定答案,绿色的部分表示我们在k这一层鸡蛋被摔碎了,下面k – 1层需要用j – 1个鸡蛋只能用确定了。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<queue>
#include<cmath>
#include<map>
#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 ++;
}

inline void re(int &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 = - x;
}

int n, m, dp[110][15];

int main()
{
    while(~ scanf("%d%d", &n, &m))
    {
        for(ri i = 1; i <= n; i ++)
            for(ri j = 0; j <= m; j ++)
                dp[i][j] = i;
        for(ri i = 1; i <= n; i ++)
            for(ri j = 1; j <= i; j ++)
                for(ri k = 2; k <= m; k ++)
                    dp[i][k] = min(dp[i][k], max(dp[j - 1][k - 1], dp[i - j][k]) + 1);
        printf("%d\n", dp[n][m]);
    }
}

【算法】最大权闭合子图

日常安利两篇文章[网络流]最大权闭合图(转载)
hiho 第119周 最大权闭合子图
闭合图是啥,就是说所有的点连出去的边都指向我们所选的点集,这就是闭合图
那么我们现在要求一个最大权的闭合图,可以通过网络流来解决
我们首先转化模型,我们将所有的正权点与源点s相连,所有的负权点与汇点t相连,原来的图流量我们都换成无穷大
首先我们来证明这么一张图上最小割是简单割
简单割的定义就是割上每条边都与起点或者汇点相连
那么首先我们可以将与起点相连的边都割掉,这些边里面没有无穷大的边,当然这种割法并不一定是最小割
那么对于最小割,它付出的代价一定小于等于刚才那种方案的代价,这就要求最小割不存在无穷大的边。因此,最小割所有的边都会与起点或者终点相连
第二步,我们要证明简单割即为闭合图,闭合图即为简单割。
如果闭合图不是简单割,必然存在一条无穷大的边,那么这个图还保持联通,与割断不相合
如果简单割不是闭合图,那么一定有无穷大的边连向另一个集合,那么这个图也是不连通的,不符合前提
那么到了最关键的一步,最大权闭合子图的权值w = 所有正权点权值之和w0 – 最小割c
证明
设最小割将点集分为两半,有源点的为点集s,有汇点的为点集t,那么最小割容量c = t内原图正权点点权之和 + s中负权点点权绝对值之和,w = s内所有正权点点权之和 – s内所有负权点绝对值之和
所以c + w = 所有正权点点权和
所以w = 所有正权点点权和
例题
luogu P2762 太空飞行计划问题
这个题就是一个比较典型的最大权闭合子图问题,我们可以将实验和仪器划分到两个集合,分别以点权的绝对值向起点/汇点建边,我们割掉与起点相连的边,说明这个实验不够优,不足以让我们去购买相应的仪器,我们割掉与终点相连的边,就说明仪器的代价要小于收益

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int
using namespace std;

const int mo = 1000000007;

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 ++;
}

char a;

bool flag;

inline void re(int &x)
{
    x = 0;
    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;
    if(a == '\r' || a == '\n')
        flag = 1;
}

int n, m, t, he, ta, lx, ans, tot = -1;

int q[500], v1[110], v2[110], de[110], head[110], hea[110];

struct in
{
    int to, ne, co;
}ter[10010];

inline void build(int f, int l, int c)
{
    ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
    ter[++ tot] = (in){f, head[l], 0}, head[l] = tot;
}

inline bool bfs()
{
    memset(de, 0, sizeof(de));
    q[he = ta = 0] = 0, de[0] = 1;
    while(he <= ta)
    {
        int qaq = q[he ++];
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(de[to] == 0 && ter[i].co > 0)
                de[to] = de[qaq] + 1, q[++ ta] = to;
        }
    }
    return de[t] > 0;
}

int dfs(int no, int fl)
{
    if(no == t || fl == 0)
        return fl;
    for(ri &i = hea[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(de[to] == de[no] + 1 && ter[i].co)
        {
            int rt = dfs(to, min(fl, ter[i].co));
            if(rt > 0)
            {
                ter[i].co -= rt, ter[i ^ 1].co += rt; return rt;
            }
        }
    }
    return 0;
}

int main()
{
    memset(head, -1, sizeof(head));
    re(m), re(n), t = n + m + 1;
    for(ri i = 1; i <= m; i ++)
    {
        re(v1[i]), ans += v1[i], flag = 0, build(0, i, v1[i]);
        while(!flag)
            re(lx), build(i, lx + m, mo);
    }
    for(ri i = 1; i <= n; i ++)
        re(v2[i]), build(i + m, t, v2[i]);
    while(bfs())
    {
        for(ri i = 0; i <= t; i ++)
            hea[i] = head[i];
        while(int ret = dfs(0, mo))
             ans -= ret;
    }
    for(ri i = 1; i <= m; i ++)
        if(de[i] > 0)
            printf("%d ", i);
    printf("\n");
    for(ri i = 1; i <= n; i ++)
        if(de[i + m] > 0)
            printf("%d ", i);
    printf("\n%d", ans);
}

luogu P2805 [NOI2009]植物大战僵尸

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#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 ++;
}

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

int h, t, ta, n, m, lx, ly, lz, tot = -1, ans, pri;

int q[1010], de[1010], num[1010], v[1010], he[1010], head[1010];

struct in
{
    int to, ne, co;
}edge[1600010], ter[1600010];

bool flag[1010];

inline int ask(int x, int y)
{
    return (x - 1) * m + y;
}

inline void build(int f, int l, int c)
{
    num[l] ++, edge[++ tot] = (in){l, he[f], c}, he[f] = tot;
}

inline void rebuild(int f, int l, int c)
{
    //cout << f << ' ' << l << ' ' << c << '\n';
    ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
    ter[++ tot] = (in){f, head[l], 0}, head[l] = tot;
}

inline void init()
{
    h = 1;
    for(ri i = 1; i <= n * m; i ++)
        if(num[i] == 0)
            q[++ t] = i;
    while(h <= t)
    {
        int qaq = q[h ++]; flag[qaq] = 1;
        for(ri i = he[qaq]; i >= 0; i = edge[i].ne)
        {
            int to = edge[i].to; num[to] --;
            if(num[to] == 0)
                q[++ t] = to;
        }
    }
    t = 0;
    for(ri i = 1; i <= n * m; i ++)
        if(flag[i] == 0)
            q[++ t] = i;
    while(h <= t)
    {
        int qaq = q[h ++]; flag[qaq] = 0;
        for(ri i = he[qaq]; i >= 0; i = edge[i].ne)
        {
            int to = edge[i].to;
            if(flag[to] == 1)
                q[++ t] = to;
        }
    } 
    tot = -1, t = n * m + 1;
    for(ri i = 1; i <= n * m; i ++)
        if(flag[i] == 1)
        {
            if(v[i] > 0)
                ans += v[i], rebuild(i, t, v[i]);
            else
                rebuild(0, i, - v[i]);
            for(ri j = he[i]; j >= 0; j = edge[j].ne)
            {
                int to = edge[j].to;
                if(flag[to] == 1)
                    rebuild(i, to, 1e9 + 7);
            }
        }
}

inline bool bfs()
{
    memset(de, 0, sizeof(de)), de[q[h = ta = 0] = 0] = 1;
    while(h <= ta)
    {
        int qaq = q[h ++];
        for(ri i = head[qaq]; i >= 0; i = ter[i].ne)
        {
            int to = ter[i].to;
            if(de[to] == 0 && ter[i].co > 0)
                de[q[++ ta] = to] = de[qaq] + 1;
        }
    }
    return de[t] > 0;
}

int dfs(int no, int fl)
{
    if(no == t)
        return fl;
    int lin = 0;
    for(ri &i = he[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(de[to] == de[no] + 1 && ter[i].co > 0)
        {
            int rt = dfs(to, min(fl - lin, ter[i].co));
            ter[i].co -= rt, ter[i ^ 1].co += rt, lin += rt;
            if(lin == fl)
                return lin;
        }
    }
    return lin;
}

/*
这个题其实是一个比较板子的最大权闭合子图,但是之前没有认真了解过
闭合子图:图内所有点的出边,都指向图内所有点构成的集合中的一个点
这个东西我们可以转化成原图正权点点权之和减去新图最小割
新图怎么建
我们现在考虑植物之间的关系,它是由一堆保护和被保护这样的东西组成的
那么对于一对这样的关系,我们从保护植物向被保护的植物建边
然后跑拓扑排序,将图中的环和受环庇护的植物去掉
那么现在就剩下了一堆一定可以被删除掉的植物
那么我们就需要考虑删除哪些植物划算哪些植物不划算了
现在还是按照保护和被保护的关系建图,流量无限 
但是我们加入一个汇点和一个源点,所有正权点向汇点连边,流量为点权
负权点向源点建边,流量为点权的绝对值
然后跑最小割,答案就是所有正点点权之和减去最小割
至于为什么这么干 我们现在最小割只会割两种边 ,与起点相连和与终点相连的边
那么对于割掉与起点有关系的点,就表示我们现在决定割掉某个植物获取更大的利益
割掉与终点有关系的点,就表示我们现在决定不要某种植物的点权来减少损失 
*/ 

int main()
{
    //freopen("qwq.out", "w", stdout);
    re(n), re(m), memset(he, -1, sizeof(he)), memset(head, -1, sizeof(head));
    for(ri i = 1; i <= n; i ++)
        for(ri j = 1; j <= m; j ++)
        {
            re(lx), v[ask(i, j)] = lx, re(lz);
            while(lz --)
                re(lx), re(ly), lx ++, ly ++, build(ask(i, j), ask(lx, ly), 1);
        }
    for(ri i = 1; i <= n; i ++)
        for(ri j = m; j > 1; j --)
            build(ask(i, j), ask(i, j - 1), 1);
    init(); 
    while(bfs())
        memcpy(he, head, sizeof(he)), ans -= dfs(0, 1e9 + 7);
    printf("%d", ans);
    return 0;
}