Dylan's Blog

CF1106F Lunar New Year and a Recursive Sequence [矩阵快速幂+EXGCD+BSGS]

Posted on 2019-02-01 Edited on 2022-09-07 In 题解

问题描述

有关系式 $fi = \left(\prod{j = 1}^{k} f{i - j}^{b_j}\right) \bmod p$，$p$ 为 $99844353$，并且设 $f_1 = f_2 = \ldots = f{k - 1} = 1$。题目告诉你 $b_1, b_2, \ldots, b_k$ 及 $f_n$，需要你求出 $f_k$。

输入

第一行一个正整数 $k$

第二行 $k$ 个整数表示 $b_1, b_2, \ldots, b_k$

第三行两个整数 $n, m$ 表示 $f_n=m$

输出

输出一个满足 $1 \leq f_k < p$ 的 $f_k$，如果有多个输出任意一个，如果不存在输出 $-1$

思路

思路不难，比较的套路，综合了很多知识点。

首先想到将系数递推关系写成矩阵的形式，然后利用矩阵快速幂将 $fn$ 写成 $f_n= \left(\prod{i = 1}^{k} f{k-i+1}^{a_i}\right) \bmod p$ 的形式，因为题目设 $f_1 = f_2 = \ldots = f{k - 1} = 1$，所以我们实际上要解一个形如 $x^a \equiv b \mod p$ 的方程。

解这个方程比较的套路。先将上面的方程写成离散对数的形式 $k^{a\log_kx} \equiv k^{\log_kb} \mod p$，再根据欧拉定理得到 $a\log_kx \equiv \log_kb \mod \varphi (p)$。其中 $k$ 应该要为 $p$ 的原根，因为这样 $k^1,k^2,…,k^{\varphi(p)}$ 是模 $\varphi(p)$ 的一个完全剩余系，这样就可以避免出现多个 $\log_kx$ 在模 $p$ 意义下的值相同。后面就很简单了，先用 BSGS 求出 $\log_kb$ 然后用 EXGCD 得到 $\log_kx$，最后用快速幂得出最终答案 $x$ 就好了。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 105
#define INF 0x3f3f3f3f
#define p 998244353
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, m, x, y, a[MAXN][MAXN], c[MAXN][MAXN], ans[MAXN][MAXN];

map<int, int> mp;

void mul(int a[MAXN][MAXN], int b[MAXN][MAXN])
{
    for(rint i=1; i<=n; ++i)
        for(rint j=1; j<=n; ++j)
        {
            c[i][j]=0;
            for(rint k=1; k<=n; ++k) c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j])%(p-1);
        }
    memcpy(a, c, sizeof(c));
}

void ksm1(int a[MAXN][MAXN], int y)
{
    for(rint i=1; i<=n; ++i) ans[i][i]=1;
    while(y)
    {
        if(y&1) mul(ans, a);
        mul(a, a); y>>=1;
    }
}

int ksm(int x, int y)
{
    int ans=1;
    while(y)
    {
        if(y&1) ans=1LL*ans*x%p;
        y>>=1; x=1LL*x*x%p;
    }
    return ans;
}

int bsgs(int a, int b)
{
    int siz=sqrt(p)+0.5, base=1;
    int t=b;
    mp[t]=0;
    for(rint i=1; i<=siz; ++i)
    {
        t=1LL*t*a%p;
        mp[t]=i;
        base=1LL*base*a%p;
    }
    t=1;
    for(rint i=1; i<=siz; ++i)
    {
        t=1LL*t*base%p;
        if(mp.count(t))
        {
            int x=i*siz-mp[t];
            return x;
        }
    }
    return -1;
}

int exgcd(int a, int b, LL& x, LL& y)
{
    if(!b)
    {
        x=1, y=0;
        return a;
    }
    int d=exgcd(b, a%b, x, y);
    int temp=x; x=y, y=temp-a/b*y;
    return d;
}

int solve(int a, int b, int c)
{
    LL x, y;
    int d=exgcd(a, b, x, y);
    //printf("%d %d %d %d!!!\n", a, b, c, d);
    if(c%d) return -1;
    x*=c/d;
    return (x%(b/d)+(b/d))%(b/d);
}

int main()
{
    scanf("%d", &n);
    for(rint i=1; i<=n; ++i) scanf("%d", &a[1][i]);
    for(rint i=2; i<=n; ++i) a[i][i-1]=1;
    scanf("%d%d", &m, &y);
    ksm1(a, m-n);
    x=solve(ans[1][1], p-1, bsgs(3, y));
    if(x==-1) printf("-1\n");
    else printf("%d\n", ksm(3, x));
    return 0;
}

USACO18OPEN Train Tracking [分块+单调队列]

Posted on 2019-01-25 Edited on 2022-06-05 In 题解

问题描述

简单来说就是限制空间，给你一个大小为 $5500$ 的数组，除该数组外不能调用其他储存。

然后有一辆长度为 $n$ 的火车，第 $i$ 节车厢上有编号 $c_i$，你需要按顺序输出每 $k$ 节车厢中的最小编号。

输入 & 输出

因为交互题，内容较多，详细内容见链接 Train Tracking 题面。

思路

我们设 $f_i$ 为从 $i-k+1$ 到 $i$ 中最小值的下标，对于 $f$ 不难想到用单调队列去优化，但是显然是不能将所有元素加入队列中，这时我们就可以利用分块。我们设 $siz$ 为块的大小，第一遍扫过去时只计算 $f_{x*siz+k}$，这样就只需要把每一个块中的最小值放入队列中，并记录下 $f_{x*siz+k}$ 给第二遍的时候用。

第二遍时我们就需要根据 $f_{x*siz+k}$ 计算出所有的 $f$。我首先可以先忽略掉下标小于 $f_0$ 的元素，然后用一个大小同为 $siz$ 的单调队列维护最前的一段，后面的只需要记录下最小值就行了。如果当前扫到的位置是所在块的最小值，那么就可以先输出这一块之前的答案，并建立新的单调队列。

代码

#include "grader.h"
/*
#include <cstdio>
#include <algorithm>
using namespace std;

int n, k, curcar, curpas, sub[5505], a[1000006];

int get(int id)
{
    return sub[id];
}

void set(int id, int val)
{
    sub[id]=val;
}

void shoutMinimum(int x)
{
    printf("%d\n", x);
}

int getTrainLength()
{
    return n;
}

int getWindowLength()
{
    return k;
}

int getCurrentCarIndex()
{
    return curcar;
}

int getCurrentPassIndex()
{
    return curpas;
}*/

void helpBessie(int val)
{
    int op=getCurrentPassIndex();
    int k=getWindowLength();
    int n=getTrainLength();
    int i=getCurrentCarIndex();
    int siz=1000, QWQ=4400, INF=0x3f3f3f3f;
    if(!op)
    {
        if(i==0) set(0, 0), set(1, -1);
        int head=get(1), tail=get(0);
        if(i%siz==0 || (i>=k && (i-k)%siz==0))
        {
            while(head>=tail && get(2*head+3)>=val) head--;
            head++;
            set(2*head+2, i);
            set(2*head+3, val);
        }
        else
        {
            int headval=get(head*2+3);
            if(val<=headval)
            {
                while(head>=tail && get(2*head+3)>=val) head--;
                head++;
                set(2*head+2, i);
                set(2*head+3, val);
            }
        }
        if(i>=k-1 && (i+1-k)%siz==0)
        {
            while(head>=tail && get(tail*2+2)<=i-k) tail++;
            set(QWQ+(i+1-k)/siz, get(tail*2+2));
        }
        set(0, tail), set(1, head);
    }
    else
    {
        if(i<get(QWQ)) return;
        if(i==get(QWQ))
        {
            set(0, 0), set(1, -1);
            set(QWQ-1, 1);
            set(QWQ-2, INF);
            set(QWQ-3, 0);
        }
        int block=get(QWQ-1), l=get(QWQ-3);
        int head=get(1), tail=get(0);
        if(i-get(QWQ+block-1)<=siz)
        {
            while(head>=tail && get(2*head+3)>=val) head--;
            head++;
            set(2*head+2, i);
            set(2*head+3, val);
        }
        else
        {
            int minnum=get(QWQ-2);
            if(val<minnum) set(QWQ-2, val);
        }
        if(l+k-1==i)
        {
            while(head>=tail && get(tail*2+2)<l) tail++;
            int a=get(QWQ-2), b=get(2*tail+3);
            shoutMinimum(a<b?a:b);
            l++;
        }
        while(siz*block+k-1<n && get(QWQ+block)==i)
        {
            while(l<=siz*block)
            {
                while(head>=tail && get(tail*2+2)<l) tail++;
                int a=get(QWQ-2), b=get(2*tail+3);
                shoutMinimum(a<b?a:b);
                l++;
            }
            block++;
            set(QWQ-2, INF);
            head=tail=0;
            set(2*head+2, i);
            set(2*head+3, val);
        }
        set(QWQ-1, block), set(QWQ-3, l);
        set(0, tail), set(1, head);
    }
}

/*
int main()
{
    scanf("%d%d", &n, &k);
    for(int i=0; i<n; ++i)
    {
        scanf("%d", &a[i]);
        curcar=i, curpas=0;
        helpBessie(a[i]);
    }
    for(int i=0; i<n; ++i)
    {
        curcar=i, curpas=1;
        helpBessie(a[i]);
    }
}*/

点分治小结

Posted on 2019-01-24 Edited on 2022-06-05 In 学习小结

一、点分治

1.BZOJ2599 Race

代码链接

2.BZOJ1468 Tree

代码链接

3.BZOJ2152 聪聪可可

代码链接

4.BZOJ5186 Cow at Large

代码链接

二、点分树

1.BZOJ4012 开店

代码链接

2.BZOJ3924 幻想乡战略游戏（坑）

三、点分治序

1.BZOJ3784 树上的路径

代码链接

四、动态点分治

（坑）

LOJ2540 随机算法 [计数类DP]

Posted on 2019-01-15 Edited on 2022-06-05 In 题解

问题描述

我们知道，求任意图的最大独立集是一类 NP 完全问题，目前还没有准确的多项式算法，但是有许多多项式复杂度的近似算法。

例如，小 C 常用的一种算法是：

对于一个 $n$ 个点的无向图，先等概率随机一个 $1$ 到 $n$ 的排列 $p[1\ldots n]$。
维护答案集合 $S$ ，一开始 $S$ 为空集，之后按照 $i=1\ldots n$ 的顺序，检查 ${p[i]}\cup S$ 是否是一个独立集，如果是的话就令 $S={p[i]}\cup S$。
最后得到一个独立集 $S$ 作为答案。

小 C 现在想知道，对于给定的一张图，这个算法的正确率，输出答案对 $998244353$ 取模

输入

第一行两个非负整数 $n,m$ 表示给定的图的点数和边数。

接下来 $m$ 行，每行有两个正整数 $(u,v) (u\neq v)$ 描述这张图的一条无向边。

输出

输出正确率，答案对 $998244353$ 取模。

思路

这题比较巧妙的地方就是设计状态。考虑比较朴素的一种方法， $0$ 表示一个点未被选，$1$ 表示一个点选了但没在集合中，$2$ 表示一个点在集合中，这样的状态数就是 $n^3$，我们需要考虑的就是如何优化这种状态。

这里要跳出按照排列的顺序选点这个思维定式。只要选了点 $i$ 加入独立集中，那么与 $i$ 相邻的点在它之后任意时候选都不会产生影响，所以假设有 $s1$ 个点没有考虑，这其中有 $s2$ 个点是与 $i$ 相邻的，那么我们考虑这 $s2$ 个点在排列中的情况数，不难发现这个就是 $A_{s1}^{s2}$。注意我们这里说的是「考虑」而不是选取，也就是说先预先给 $s2$ 个点排好位置，而不是按照排列的顺序依次选了这些点。

所以我们可以这样设计状态，设 $f_{S, i}$ 为考虑了集合 $S$ 且其中独立集大小为 $i$ 的方案数。按照上文提到的考虑方法，可以知道只要是不属于集合 $S$ 的点一定可以加入 $S$ 中的独立集，因为与独立集相邻的点已经在 $S$ 中了。设已经考虑了点集 $S$ ，此时要加入点 $k$，与$k$ 相邻的点集为 $e_k$，还有 $s1$ 个点没有考虑，这其中有 $s2$ 个点是与 $k$ 相邻的，有转移方程

$f\_{S \\bigcup e\_k, i+1} +=f\_{S, i} \* A\_{s1}^{s2}$

其中 $k\notin S$，$s1=n-|S|-1$，$s2=|e_k\bigcap(e_k\bigcup S)|$。这样转移总复杂度就是 $O(n^22^n)$ 了。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 25
#define MAXM (1<<20)+5
#define INF 0x3f3f3f3f
#define p 998244353
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, m, e[MAXN], f[MAXM][MAXN], bit[MAXM], fac[MAXN], inv[MAXN];

void init()
{
    fac[0]=fac[1]=inv[0]=inv[1]=1;
    for(rint i=0; i<(1<<n); ++i) bit[i]=bit[i>>1]+(i&1);
    for(rint i=2; i<=n; ++i) inv[i]=1LL*inv[p%i]*(p-p/i)%p;
    for(rint i=2; i<=n; ++i)
    {
        inv[i]=1LL*inv[i]*inv[i-1]%p;
        fac[i]=1LL*fac[i-1]*i%p;
    }
}

int A(int x, int y)
{
    return 1LL*fac[x]*inv[x-y]%p;
}

int main()
{
    scanf("%d%d", &n, &m);
    init();
    for(rint i=1, x, y; i<=m; ++i)
    {
        scanf("%d%d", &x, &y);
        x--, y--;
        e[x]|=(1<<y);
        e[y]|=(1<<x);
    }
    for(rint i=0; i<n; ++i) e[i]|=(1<<i);
    f[0][0]=1;
    for(rint sta=0; sta<(1<<n); ++sta)
        for(rint i=0; i<n; ++i)
        {
            if(!f[sta][i]) continue;
            for(rint j=0; j<n; ++j)
                if(!((sta>>j)&1))
                {
                    int nxt=sta|e[j], s1=n-bit[sta]-1, s2=bit[e[j]^(e[j]&sta)]-1;
                    f[nxt][i+1]=(f[nxt][i+1]+1LL*f[sta][i]*A(s1, s2)%p)%p;
                }
        }
    for(rint i=n; i>=0; i--)
        if(f[(1<<n)-1][i])
        {
            printf("%lld\n", 1LL*f[(1<<n)-1][i]*inv[n]%p);
            return 0;
        }
    return 0;
}

LOJ2538 Slay the Spire [计数类DP]

Posted on 2019-01-10 Edited on 2022-06-05 In 题解

问题描述

九条可怜在玩一个很好玩的策略游戏：Slay the Spire，一开始九条可怜的卡组里有 $2n$ 张牌，每张牌上都写着一个数字 $w_i$,一共有两种类型的牌，每种类型各 $n$ 张：

攻击牌：打出后对对方造成等于牌上的数字的伤害。

强化牌：打出后，假设该强化牌上的数字为 $x$，则其他剩下的攻击牌的数字都会乘上 $x$。保证强化牌上的数字都大于 $1$。

现在九条可怜会等概率随机从卡组中抽出 $m$ 张牌，由于费用限制，九条可怜最多打出 $k$ 张牌，假设九条可怜永远都会采取能造成最多伤害的策略，求她期望造成多少伤害。

假设答案为 $ans$，你只需要输出 $ans * \frac{(2n)!}{m!(2n-m)!} \mod 998244353 $

输入

第一行一个正整数 $T$ 表示数据组数接下来对于每组数据：第一行三个正整数 $n,m,k$ 第二行 $n$ 个正整数 $w_i$，表示每张强化牌上的数值第三行 $n$ 个正整数 $w_i$，表示每张攻击牌上的数值

输出

输出 $T$ 行，每行一个非负整数表示每组数据的答案。

思路

首先题目要求的其实是所有 ${2n \choose m}$ 种情况造成的伤害之和，是一个计数问题。

有一个很巧妙的条件是「强化牌上的数字是大于 1 的整数」我们可以据此得出最优策略是：如果强化牌数量大于 $i$，那么就先用最大的 $k-1$ 张强化牌，再用最大的 $1$ 张攻击牌；否则就是先用掉所有强化牌，再用最大的 $k-i$ 张攻击牌。

先将两种牌从大到小排序，设计状态 $f_{i,j}$ 为用了$i$ 张牌最小的牌为 $w_j$ 所有这种情况的强化倍数之和；$g_{i,j}$ 为用了$i$ 张牌最小的牌为 $w[j]$ 所有这种情况的总伤害之和。它们的转移方程分别为 $f\_{i,j}=w\_j \* \\sum\_{k=1}^{j-1} f\_{i-1,k}$ $g\_{i,j}=w\_j\*{i-1 \\choose j-1}+ \\sum\_{k=1}^{j-1} g\_{i-1,k}$ 但是这样还不够，我们还要考虑每一个状态所对应的情况数。设 $F_{i,j}$ 为抽到了 $i$ 张强化牌，并使用了其中 $j$ 张的情况的总强化倍数乘对应情况数；$G_{i,j}$ 为抽到了 $i$ 张攻击牌，并使用了其中 $j$ 张的情况的总伤害乘对应情况数。$F_{i,j},G_{i,j}$ 满足式子 $F\_{i,j}=\\sum\_{k=1}^{n} f\_{j,k}\*{n-k \\choose i-j}$ $G\_{i,j}=\\sum\_{k=1}^{n} g\_{j,k}\*{n-k \\choose i-j}$ 这时候我们最初提到的最优策略就要用到了，我们先枚举 $m$ 张牌的类型，然后根据最优策略算出对应的贡献。因此答案就是 $ans=\\sum\_{i=0}^{m-1} F\_{i,min(i,k-1)}\* G\_{m-i,max(k-i)}$

最后是实现的细节，我们先预处理 $f_{i,j}$ 和 $g_{i,j}$，利用前缀和可以做到 $O(n^2)$。然后我们可以在计算答案时对于每一个 $F_{i,j},G_{i,j}$ 用 $O(n)$ 计算出来，这样总复杂度就是 $O(n^2)$ 的。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 3005
#define INF 0x3f3f3f3f
#define p 998244353
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int T, n, m, k, ans, w[MAXN], v[MAXN], f[MAXN][MAXN], g[MAXN][MAXN];
int inv[MAXN], fac[MAXN];

bool CMP(int x, int y)
{
    return x>y;
}

void init()
{
    inv[0]=inv[1]=fac[0]=fac[1]=1;
    for(rint i=2; i<=3000; ++i) inv[i]=1LL*inv[p%i]*(p-p/i)%p;
    for(rint i=2; i<=3000; ++i)
    {
        inv[i]=1LL*inv[i-1]*inv[i]%p;
        fac[i]=1LL*fac[i-1]*i%p;
    }
}

int comb(LL x, LL y)
{
    if(y>x) return 0;
    return 1LL*fac[x]*inv[y]%p*inv[x-y]%p;
}

int calf(int x, int y)
{
    int sum=0;
    if(y==0) return comb(n, x);
    for(rint i=1; i<=n; ++i)
        sum=(sum+1LL*f[y][i]*comb(n-i, x-y))%p;
    return sum;
}

int calg(int x, int y)
{
    int sum=0;
    for(rint i=1; i<=n; ++i)
        sum=(sum+1LL*g[y][i]*comb(n-i, x-y))%p;
    return sum;
}

int main()
{
    init();
    scanf("%d", &T);
    while(T--)
    {
        ans=0;
        scanf("%d%d%d", &n, &m, &k);
        for(rint i=1; i<=n; ++i) scanf("%d", &w[i]);
        for(rint i=1; i<=n; ++i) scanf("%d", &v[i]);

        sort(w+1, w+n+1, CMP);
        sort(v+1, v+n+1, CMP);
        for(rint i=1; i<=n; ++i)
            g[1][i]=v[i], f[1][i]=w[i];
        for(rint i=2; i<=n; ++i)
        {
            int sum1=0, sum2=0;
            for(rint j=1; j<=n; ++j)
            {
                f[i][j]=1LL*w[j]*sum1%p;
                g[i][j]=(1LL*comb(j-1, i-1)*v[j]+sum2)%p;
                //printf("%d %d %d %d %d!!!\n", i, j, sum2, w[j]);
                sum1=(sum1+f[i-1][j])%p;
                sum2=(sum2+g[i-1][j])%p;
            }
        }
        //for(rint i=1; i<=n; ++i)
        //  for(rint j=1; j<=n; ++j) printf("%d %d %d %d!!!\n", i, j, f[i][j], g[i][j]);
        for(rint i=0; i<m; ++i)
        {
            int a=calf(i, min(i, k-1));
            int b=calg(m-i, max(1, k-i));
            ans=(ans+1LL*a*b)%p;
            //printf("%d %d %d!!\n", ans, a, b);
        }
        printf("%d\n", ans);
    }
    return 0;
}