Hzao's Blog

题解 UVA11361 【Investigating Div-Sum Property】

数位DP，对于每一个询问，回答为 $ask(B)-ask(A-1).$

我主要想分享一下一些实现上的细节。但还是先说一下思路，这里借鉴了《算法竞赛入门经典:训练指南》的讲解。

设 $f(w,m_1,m_2)$ 表示有 $w$ 位数（可以有前导 $0$ ）需要确定，需要让各位数字之和除以 $K$ 的余数为 $m_1$ ，需要让这 $w$ 位数组成的数字除以 $K$ 的余数为 $m_2$ 需要的方案数。然后我们一步一步确定前面几位数，加起来得到答案。

显然，我们可以从 $0$ 到 $9$ 枚举最高位上的数字 $head$ ，从而有:

$f(w,m_1,m_2)=\sum f(w-1,(m_1 - head)mod \, K,(m_2 - 10^{w-1}head)mod \,K).$

边界: $f(0,0,0)=1$ ， $f(0,m_1 ≠0,m_2≠ 0)=0.$

理解：要让 $w$ 位数各个位之和 $mod \, K$ 为 $m_1$ ，且第一位为 $head$ ，那么肯定需要没有 $head$ 的时候 $mod \, K$ 的值为为 $(m_1-head)mod \, K$ 。第三个参数亦然。

几个细节：

$1.$ 记忆化搜索，那么时间复杂度为 $O(ws* K^2).$ 可是 $K$ 这么大怎么办？

如果 $ask(val)$ 中 $val$ 有 $ws$ 位数，但是 $K > 9* ws$ ，显然没有合法的数字。因为所有位加起来都没有 $K$ 那么大，肯定加起来之后不能整除 $K$ .

所以题中数据范围给那么大是没用的…..

于是可以用数组来记搜，数字最多十位数，所以 $K>9 * 10 =90$ 时肯定是无解的。数组可以开得下。

$2.$ $val=0$ 时答案为 $1$ 不为 $0$ 。

$3.$ 可以先让 $val=val+1$ ，然后紧贴 $val$ 求解答案，需要同时记录已经有的各位数字之和和总的数字之和。

还有一些细节见代码：

#include<cmath>
#include<cstdio>
#include<cstring>
template<typename T>
inline bool read(T &x){
    x=0;char c;T  f=1;
    do{c=getchar();if(c=='-')f=-1;else if(c==EOF)return false;}while(c>'9'||c<'0');
    do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');
    return x*=f,true;
}
long long A,B,K;
long long tp[20];//tp[i]表示10 的i次方
long long Div[20];
long long d[20][200][200];

#define res1 (d[w][m1][m2])
long long f(int w,int m1,int m2){
    if(w==0){
        return m1==0&&m2==0;
    }
    if(~d[w][m1][m2])return d[w][m1][m2];
    res1=0;
    for(register int  i=0;i<=9;++i){
        //i即为前所述的head 即最高位的数字
        res1+=f(w-1,(m1-i%K+K)%K,(m2-(1ll*tp[w-1]*i%K)+K)%K);
        //必须保证mod K之前为非负数 所以加上一个K 
    }
    return res1;
}
long long Getws(long long val){//分割这个数，并且返回它的位数

    if(!val){//其实这步可以不要。毕竟在GetAns()的入口处特判了0的情况
        return Div[0]=(Div[1]=0)+1;
    }
    Div[0]=0;
    while(val){
        Div[++Div[0]]=val%10;
        val/=10;
    }
    return  Div[0];
}
long long GetAns(long long val){
    if(!val)return 1ll;
    long long res=0;
    ++val;
    //紧贴val来计算答案，如果不加1会漏掉val这个数
    //当然也可以不加1，最后特判val这个数
    long long ws=Getws(val);
    if(ws*9<K)return 1ll;
    long long presum=0,presum2=0;
    //presum：当前累计的各位数字之和 如322的presum=3+2+2=7
    //presum2：当前已确定数字组成的数：如32***的presum2=32000.
    for(register int  i=ws;i>=1;--i){
        for(register int  j=0;j<Div[i];++j){
            if(j)presum+=1;presum%=K;
            if(j)presum2+=tp[i-1];presum2%=K;
            //presum,presum2每步取模更方便
            res+=f(i-1,(K-presum+K)%K,(K-presum2+K)%K);
            //此处有减法，必须保证它是非负数
        }
        //紧贴val来取值，则最高一位没有被讨论到
        //例如，如果val=32565
        //如果已经枚举到第二位
        //那么实际上我们暂时只会先考虑30***和31***的情况
        //但在后面的讨论中，应保证第二位为2
        //所以还要把2的贡献累加进去
        if(Div[i]){
            ++presum;
            presum2+=tp[i-1];
        }
    }
    return res;
}
void  work(){
    // GetAdd();
    long long ans=GetAns(B)-GetAns(A-1);
    printf("%lld\n",ans);
}
int main(){
    //freopen("testin.txt","r",stdin);
    //freopen("testout.txt","w",stdout);
    tp[0]=1;
    for(register int  i=1;i<=15;++i){
        tp[i]=10ll*tp[i-1];
    }
    long long T;
    read(T);
    while(T--){
        read(A);
        read(B);
        read(K);
        memset(d,-1,sizeof(d));
        work();
    }

    return 0;
}

题解 UVA1073 【Glenbow Museum】

如果有一个点能看到各个顶点，那么这个点的上下左右一定要对应四个 $RR$ 。

如果有 $OO$ ，那么这两个 $270$ °的角延伸出去的角的可视范围没有交集，即它们不能被同时被看到（点 $A$ 能看到点 $B$ ，那么点 $B$ 也能看到点 $A$ 。反之 $B$ 一定不能看到点 $A$ ），如下图所示：（延伸出去的角可能是 $R$ 也可能是 $O$ ，这里以 $R$ 为例）

所以一定不能有 $OO$ 。

如果没有 $OO$ ，但是有 $OR$ 。那么 $OR$ 前面一个字符一定是 $R$ 。（否则就有 $OO$ 了）。这 $O,R$ 两个角的可视范围是有交集的。如下图所示：

同样地，相邻的 $RR$ 两角的可视范围也是有交集的。至少它们两个角是可以被同时看到的。

如果一个点能看到所有内角，那么它的正对的上下左右一定都是 $RR$ 。因为如果某个方向是 $RR$ ，显然成立。如果某个方向上的角度序列有 $OR$ ，那么这个方向的角度序列只能是 $OROROR…ORR$ 。即只能以 $RR$ 结尾。（如果一直不结尾，那就不构成多边形。如果以 $OO$ 结尾，那么不合法）。

既然以 $RR$ 结尾，那么能同时看到这个 $RR$ 的点一定在如图所示的灰色区域。

反过来说，一个点的正对的上下左右四个方向一定是 $RR$ 。

稍加思考可以发现，只要满足上下左右四个方法有 $RR$ ，且整个序列没有 $OO$ ，那么一定满足条件。(没有 $OO$ 意味着不会往外拐)

$L$ 个内角代表 $L$ 条边，根据多边形内角和公式：
$90R+270O=(L-2)* 180.$

又因为 $R+O=L.$

所以有 $R=(L+4)/2,O=(L-4)/2.$

所以我们要求的就是 $(L+4)/2$ 个 $R$ 和 $(L-4)/2$ 个 $R$ 的字符串中，有至少四个 $RR$ 且没有 $OO$ 的个数。注意 $L<4$ 或者 $L$ 为奇数时无解。（为奇数时的内角和不为 $180$ °的整数倍）

前两个实现方法参考《算法竞赛入门经典：训练指南》:

方法一：

用 $f(i,j,b,e)$ 表示有 $i$ 个 $R$ ， $j$ 个 $O$ ，开头为 $b$ （ $0$ 表示 $R$ ， $1$ 表示 $O$ ），结尾为 $e$ 。

则 $f(x,0,0,0)=f(0,1,1,1)=1,x > 0.$

且 $f(i,j,b,0)=f(i-1,j,b,1)+f(i-1,j,b,0).$

$f(i,j,b,1)=f(i,j-1,b,0).$ （不能出现 $OO$ ）

答案就很显然了（把几个 $f(i,j,b,e)$ 加起来），你可以自行推一推或者见代码。

递归加上记忆化即可 $O(n)$ 解决。（直接递推则需 $O(n^2)$ ）

代码：

#include<cstdio>
#include<cstring>
int L,kase;
long long d[520][520][2][2];
long long f(int i,int j,int b,int e){
    if(~d[i][j][b][e]){
        return d[i][j][b][e];
    }
    if(!j){
        return i&&!b&&!e;
    }
    if(!i){
        return j==1&&b==1&&e==1;
    }
    if(e){
        return d[i][j][b][e]=f(i,j-1,b,0);
    }
    else{
        return d[i][j][b][e]=f(i-1,j,b,0)+f(i-1,j,b,1);
    }
}
int main(){
    memset(d,-1,sizeof(d));
    long long ans;
    while(~scanf("%d",&L)&&L){
        ans=0;
        if(!(L&1||L<4)){
            ans+=f((L+4)/2,(L-4)/2,0,0);
            ans+=f((L+4)/2,(L-4)/2,1,0);
            ans+=f((L+4)/2,(L-4)/2,0,1);
        }
        printf("Case %d: %lld\n",++kase,ans);
    }
    return 0;
}

方法二：

$d(i,j,k)$ 表示以 $k$ 开头，有 $i$ 个 $R$ ，有 $j$ 对相邻的 $R$ （ $RRR$ 算两对， $ROR$ 算 $0$ 对），且以 $R$ 结尾的方案数。

则 $d(1,0,0)=d(1,0,1)=1.$

其余 $d(i,j,k)=d(i-1,j,k)+d(i-1,j-1,k)$ .表示当前字符串可由某个 $R$ 结尾的字符加上 $OR$ 或 $R$ 来得到。

设 $A=(L+4)/2$ 。

答案是 $d(A,4,1)+d(A,3,0)+d(A,4,0).$

第一项表示 $O$ 开头 $R$ 结尾。

第二项表示 $R$ 开头 $R$ 结尾。求的是字符串中只有 $3$ 对 $RR$ 。但是把开头和结尾这一对算上就有 $4$ 对了。

第三项很难理解，它表示 $R$ 开头 $O$ 结尾。每一个 $R$ 开头 $O$ 结尾的合法字符串都对应一个把最后一个 $O$ 去掉之后的， $R$ 开头 $R$ 结尾的字符串。因为最后一个字符是 $O$ ，不能和前面的 $R$ 接在一起，所以需要保证前面就有 $4$ 个 $R$ 。

也就是说把 $4$ 个 $RR$ 对的 $R$ 开头 $R$ 结尾的字符串后面加上一个 $O$ 就可以得到 $4$ 个 $RR$ 对的 $R$ 开头 $O$ 结尾的字符串。

代码：

#include<cstdio>
#include<cstring>
int L,kase;
long long d[520][520][2];
long long f(int i,int j,int k){
    if(i==1){
        return !j;
    }
    if(~d[i][j][k])return d[i][j][k];
    return d[i][j][k]=f(i-1,j,k)+f(i-1,j-1,k);
}
int main(){
    memset(d,-1,sizeof(d));
    while(~scanf("%d",&L)&&L){
        if(L&1||L<4){
            printf("Case %d: 0\n",++kase);
            continue;
        }
        printf("Case %d: %lld\n",++kase,
            f((L+4)/2,3,0)+//R...R
            f((L+4)/2,4,1)+//O...R
            f((L+4)/2,4,0)  //R...O
        );
    }
    return 0;
}

方法三：（参考了KobeDuu的博客）

组合计数。

其实可以发现，只要有 $A=(L+4)/2$ 个 $R$ ， $B=(L-4)/2$ 个 $O$ (其实 $B=A-4$ )，并且 $OO$ 不相连，那么一定可以保证有4个 $RR$ 对。

可以这样想：把 $A \ge 4$ 个 $R$ 连成一个环，那么有 $A$ 个 $RR$ 对。

再把 $B=A-4$ 个 $O$ 插入，每插入一个 $O$ ，就会少一个 $RR$ 对。

所以最后剩下 $A-B=4$ 个 $RR$ 对。刚好满足条件。

所以可以这样利用组合数算,把所有 $RR$ 排成一行之后：

$1.$ 在开头放 $O$

那么，最后一个位置不能放 $O$ 。剩下 $A-1$ 个位置可以放，要放下 $B-1$ 个 $O$ 。

计数 $C_{A-1}^{B-1}$

$2.$ 不在开头放 $O$

那么剩下 $A$ 个位置可以放 $B$ 个 $O$ 。
计数 $C_{A}^{B}.$

所以答案为 $C_{A-1}^{B-1}+C_{A}^{B}.$

代码太简单就略了吧。

祝AC。

题解 UVA11806 【Cheerleaders】

以下内容中 $C_{n}^{m}$ 表示组合数。

考虑四角上四个点的情况:

$1.$ 四个角都不放人。

显然需要枚举最外圈（第一行、最后一行、第一列、最后一列的并集）除开四个角之外的放置方案。

设第一列、最后一列、第一行、最后一行中除开第一个位置和最后一个位置分别放置 $j_1,j_2,k_1,k_2$ 个人，那么它们分别有： $C_{n-2} ^{j_1},C_{n-2}^{j_2}, C_{m-2}^{k_1},C_{m-2}^{k_2}$ 种放置方法。(需要保证 $1 \leq j_1,j_2,k_1,k_2 <k$ 且 $j_1+j_2+k_1+k_2 \leq k$ )

除开最外圈，里面还剩下 $left=k-(j_1+j_2+k_1+k_2)$ 个人，需要把他们放置在中间共 $(m-2) (n-2)$ 个位置上。有 $C_{(m-2) (n-2)}^{left}$ 种方法。

所以一共有 $( \sum C_{n-2}^{j_1} C_{n-2}^{j_2} C_{m-2}^{k_1} C_{m-2}^{k_2}) C_{(m-2) (n-2)}^{left}$ 种方案。

(也就是说要枚举 $j_1,j_2,k_1,k_2$ )

$2.$ 仅一个角放人。 那么又有四种情况:左上、左下、右上、右下。显然这四种是等价的，求一种之后乘以 $4$ 即为答案。

为了方便讲述，假设选择了左上的那一个角。

那么第一行、第一列都不需要找了。为了使方案合法，我们需要一种方案，使得最后一行、最后一列都有人。

因为左下、右上、右下都不放人，所以最后一列 $n-2$ 个位置中至少要选择一个人，最后一行 $m-2$ 个位置中要选择至少一个人。

假设最后一列放 $j_1$ 个人，最后一行放 $k_1$ 个人，那么方案数为 $C_{n-2}^{j_1} C_{m-2}^{k_1}$ .

除去左上角一个点、最后一整列、最后一整行，还剩下 $(m-1) (n-1)-1$ 个点可以放人，还剩下 $k-j_1-k_1-1$ 个人需要放。

于是放这剩下的 $k-j_1-k_1-1$ 个人就有 $C_{(m-1) (n-1)-1}^{k-j_1-k_1-1}$ 种方法。

于是这种情况下有 $(\sum C_{n-2}^{j_1} C_{m-2}^{k_1}) C_{(m-1) (n-1)-1} ^ { k-j_1-k_1-1}$ 种方法。

3.有且只有两个角放人。

假设这两个人不在同一对角线上 ：

那么只有在 $n>2$ 时才能在左上左下、右上右下放置。只有在 $m>2$ 时才能在左上右上、左下右下放置。(否则若要满足情况，则不止要放 $2$ 个角)。

假设 $n>2$ 且在左上左下(或者右上右下)放置，那么只有最后一列(或者第一列)没有被覆盖了。我们需要在最后一列(或者第一列)的 $n-2$ 个位置上选出至少一个人来参与。设选择 $j$ 人，那么方案数为 $C_{n-2}^{j}$ 。

还剩下 $left=k-2-j$ 个人，放置在 $nm-2-n$ 个位置。

方案数为 $(\sum C_{n-2}^{j}) C_{n m-2-n}^{left}$ 。
由于可以选左上左下或者右上右下，所以需要把这个玩意乘以 $2$ 。

同理，如果 $m>2$ 且选择左上右上（或者左下右下)，给最后一行（或者第一行）放置 $j$ 个人，那么方案数共为： $(\sum C_{m-2}^{j}) C_{n m-2-m}^{left}$ 。同样需要计数时乘以 $2$ 。

假设在同一对角线上：

除了四个角，每个位置都可以放置，方案数为 $C_{n m-4}^{k-2}$ 。在对角线上有两种情况（左上右下，左下右上），所以这个数也要乘以 $2$ 。

4.有且只有三个角放人。

那么无论怎么放，都是满足条件的。
$4$ 个点中选出 $3$ 个有 $C_{4}^{3}$ 种方法，除开四角有 $C_{n m - 4}^{k-3}$ 种方法。

所以计数： $C_{4}^{3}C_{nm-4}^{k-3}$ 。

5.所有角都放人。

那么所有角都放人有一种方法，除开这四个角共有 $C_{n m -4}^{k-4}$ 种方法，所以计数 $C_{nm-4}^{k-4}$ 。

当然要记得每步取模。

代码:

#include<cstdio>
#include<cstring>
// #define LOC

const long long mod=1000007;
long long C[505][505];
long long n,m,k;
long long ans;
long long T;
int kase;
void init(){
    C[0][0]=1;
    for(register int i=1;i<=500;++i){
        C[i][0]=1;
        for(register int j=1;j<=i;++j){
            C[i][j]=C[i-1][j-1]+C[i-1][j];
            C[i][j]%=mod;
            // printf("C[%d][%d]=%lld\n",i,j,C[i][j]);
        }
    }
}

void work(){
    scanf("%lld%lld%lld",&n,&m,&k);
    ans=0;
    if(m*n>=k){
        {//四个角都不放人
            for(register int j1=1;j1<=n-2;++j1){
                if(j1>=k)continue;
                for(register int j2=1;j2<=n-2;++j2){
                    if(j1+j2>=k)continue;
                    for(register int k1=1;k1<=m-2;++k1){
                        if(j1+j2+k1>=k)continue;
                        for(register int k2=1;k2<=m-2;++k2){
                            if(j1+j2+k1+k2>k)continue;
                            ans+=C[n-2][j1]*C[n-2][j2]%mod*C[m-2][k1]%mod*C[m-2][k2]%mod*C[(m-2)*(n-2)][k-(j1+j2+k1+k2)]%mod;
                            ans%=mod;
                        }
                    }
                }
            }
            ans%=mod;
        }

        {// 一个角上放人
            for(register int j1=1;j1<=n-2&&j1<k;++j1){
                for(register int k1=1;k1<=m-2;++k1){
                    if(j1+k1+1>k)continue;
                    ans+=C[n-2][j1]*C[m-2][k1]%mod*C[(m-1)*(n-1)-1][k-1-j1-k1]%mod*4%mod;
                    ans%=mod;
                }
            }
            ans%=mod;
        }

        {//左上左下或者右上右下放置
            for(register int j=1;j<=n-2&&j<=k-2;++j){
                ans+=C[n-2][j]*C[m*n-n-2][k-2-j]%mod*2%mod;
                ans%=mod;
            }
            ans%=mod;
        }

        {//左上右上或者左下右下放置
            for(register int j=1;j<=m-2&&j<=k-2;++j){
                ans+=C[m-2][j]*C[m*n-m-2][k-2-j]%mod*2%mod;
                ans%=mod;
            }
            ans%=mod;
        }


        if(k>=2){//对角线上放置
            ans+=2*C[m*n-4][k-2];
            ans%=mod;
        }

        if(k>=3){//三个角都放
            ans+=C[4][3]*C[m*n-4][k-3]%mod;
            ans%=mod;
        }

        if(k>=4){//四个角都放
            ans+=C[m*n-4][k-4];
            ans%=mod;
        }
    }
    printf("Case %d: %lld\n",++kase,ans);
}
int main(){
    scanf("%lld",&T);
    init();
    while(T--){
        work();
    }
    return 0;
}

早睡身体好

去年今天我第一次来3-2机房。

回翻手机相册发现自己记下好多没用的东西。

/*******/

好多惊喜统统镇定

删掉一半应用把复杂消融成简单

早睡身体好

几道水题的题解

这篇文章包含了这几道简单题的题解：

逆序排列

给出 $2$ 个数 $n$ 和 $k$ ，求 $1~n$ 的全排列中，逆序数为 $k$ 的排列有多少种。每个测试点包含 $T$ 组数据。
$1 \leq T \leq 10000, 2 \leq n \leq 1000, 0 \leq k \leq 20000$

$1$ 到 $n$ 的全排列有 $n!$ 个，每个测试点的数据组数很多。考虑动态规划。

和1296 有限制的排列一样，假如以“当前考虑到 $1$ 到 $N$ 的全排列的第 $i$ 位，且逆序对数为 $j$ 的排列个数”来定义状态 $d[i][j]$ ，必然会困于如何去重。即使找到去除重复数字的方法，也会导致时间复杂度偏高。

因此我们这样简化状态：定义 $d[i][j]$ 为 $1$ 到 $i$ 的全排列中，逆序对数为 $j$ 的排列数。可以发现 $d[n][j]$ 仍然包含了所需要的状态。

如何由 $1$ 到 $(i-1)$ 的全排列转移到 $1$ 到 $i$ 的全排列？怎么保证没有重复的数字？假如新排列第 $i$ 位是 $j$ ，这些新排列和 $1$ 到 $(i-1)$ 的全排列的关系是什么？

借鉴 1296 有限制的排列的思想（这两道题的在思想上很相像），我们可以把每一个 $1$ 到 $(i-1)$ 的全排列通过以下方式变成一个长度为 $i$ ，且最后一位为 $j$ 的全排列：

将原排列中，大于等于 $j$ 的数加上1；
在最后添上 $j$ 。

可以发现每个 $1$ 到 $(i-1)$ 的全排列都可以转化为各不相同的长度为 $i$ ，且最后一位为 $j$ 的全排列。（从数学上理解，最后一位确定，前 $i-1$ 位的排列数为 $(i-1)!$ ，也就是 $1$ 到 $(i-1)$ 的全排列个数。）

在理解上述内容的基础上，我们可以得到状态转移方程:

$d[i][j]=\sum_{k=1}^i d[i-1][j-(i-1-k+1)] = \sum_{k=1}^i d[i-1][j-(i-k)]$

在给第 $i$ 位填上 $k$ 后，前面大于 $k$ 的 $i-k$ 个数就会和 $k$ 构成逆序对。因此需要满足在转移之前有 $j-(i-k)$ 个逆序对。注意，这里计算的大于 $k$ 的个数，是指新排列中大于 $k$ 的个数。即在长度为 $i-1$ 的原排列中大于等于 $k$ 的个数。

由于频繁求区间和，可以考虑维护前缀和。长度为 $i$ 的全排列的状态只与长度为 $i-1$ 的全排列的状态有关，所以考虑滚动数组。

时间复杂度 $O(nk+TlogT)$

代码如下：

#include<cstdio>
#include<algorithm>
#include<cstring>
using std::sort;
const long long maxn=1000,mod=1e9 + 7;
long long n,k,done=1;
long long ans[10*maxn+5];
long long sum[2][20005];
struct qst{
    long long n,k,id;
}Q[maxn*10+5];
inline void read(long long &x){
    x=0;char c;long long f=1;
    do{
        c=getchar();if(c=='-')f=-1;
    }
    while(c>'9'||c<'0');
    do{
        x=x*10+c-'0';c=getchar();
    }
    while(c>='0'&&c<='9');
    x*=f;
}
inline long long max(long long a,long long b){
    return a>b?a:b;
}
long long d[2][20005];
void work(){
    d[0][0]=1;
    sum[0][0]=1;
    for(register int i=1;i<=k;++i){
        sum[0][i]=1;
    }
    for(register long long i=1;i<=n;++i){
        for(register long long nk=0;nk<=k;++nk){
            d[i&1][nk]=0;
            d[i&1][nk]=(sum[(i-1)&1][nk]-(nk-i>=0?sum[(i-1)&1][nk-i]:0)+mod)%mod;
            if(i==Q[done].n&&nk==Q[done].k){
                ans[Q[done++].id]=d[i&1][nk];
            }
            sum[i&1][nk]=((nk?sum[i&1][nk-1]:0)+d[i&1][nk])%mod;
        }
    }
}
inline bool cmp(qst a,qst b){
    if(a.n!=b.n)return a.n<b.n;
    return a.k<b.k;
}
int main(){
    long long T;
    read(T);
    for(register long long i=1;i<=T;++i){
        read(Q[i].n);
        read(Q[i].k);
        n=max(n,Q[i].n);
        k=max(k,Q[i].k);
        Q[i].id=i;
    }
    sort(Q+1,Q+1+T,cmp);
    work();
    for(register long long i=1;i<=T;++i){
        printf("%lld\n",ans[i]);
    }
    return 0;
}

最长递增路径

一个无向图，可能有自环，有重边，每条边有一个边权。你可以从任何点出发，任何点结束，可以经过同一个点任意次。但是不能经过同一条边2次，并且你走过的路必须满足所有边的权值严格单调递增，求最长能经过多少条边。
$1 \leq N \leq 50000, 0 \leq M \leq 50000, 0 \leq W \leq 10^9$

有点像最长上升子序列，只不过是在图上。

考虑将每条无向边拆成两条有向边，按照边的大小排序，由于一条路径走过后不能再走，所以没有后效性。

每次从边 $a$ 转移到边 $b$ ，需要满足两个条件：

$a$ 的终点是 $b$ 的起点。
$a$ 的长度必须严格小于 $b$ 的。

考虑用数组 $maxb[]$ 保存每个节点作为终点的，已经走过的最长的边数。那么通过某条边从一个点 $u$ 走向另一个点 $v$ 时，可以用 $maxb[u]+1$ 来更新 $maxb[v]$ 。为了满足第二点，我们可以以边长为标准分段，将某几条长度相同的边处理完之后，再一起更新这些边更新过的 $maxb[]$ 。

时间复杂度 $O(mlogm)$

代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
using std::sort;
const int maxn=5e4;
struct line{
    int u,v,w;
}l[maxn*2+5];
int ans;
int d[maxn*2+5],maxb[maxn+5];
inline void read(int &x){
    x=0;char c;int f=1;
    do{c=getchar();if(c=='-')f=-1;}while(c>'9'||c<'0');
    do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');x*=f;
}
inline bool cmp(line a,line b){
    return a.w<b.w;
}
int n,m;

int main(){
    read(n);read(m);
    for(register int i=1;i<=m;++i){
        read(l[i].u);read(l[i].v);read(l[i].w);
        l[i+m].w=l[i].w;
        l[i+m].u=l[i].v;
        l[i+m].v=l[i].u;
    }
    sort(l+1,l+1+2*m,cmp);
    int lst=1;
    for(register int i=1;i<=2*m;++i){
        if(l[i].w!=l[lst].w){
            for(register int j=lst;j<i;++j){
                maxb[l[j].v]=std::max(maxb[l[j].v],d[j]);
            }
            lst=i;
        }
        d[i]=maxb[l[i].u]+1;
        if(d[i]>ans)ans=d[i];
    }
    printf("%d\n",ans);
    return 0;
}

选数字

当给定一个序列a[0],a[1],a[2],…,a[n-1] 和一个整数K时，我们想找出,有多少子序列满足这么一个条件：把当前子序列里面的所有元素乘起来恰好等于K。每个测试点包含不超过20组数据， $1 \leq n \leq1000,2 \leq K \leq 100000000$

很显然是一道动态规划题。

读入一个数字，就可以用它与前面的数字能构成的数来构成新的数（或者给已有的数增加方案数）。这算是最普通的做法。

给出一种优化：

读入 $a[i]$ 时，假如 $k \bmod a[i]\ne0$ ，则直接忽略，读入下一个数字。
用 $a[i]$ 与之前已经生成的某个数 $x$ 构成新的数时，若 $k \bmod (x*a[i])\ne0$ 则跳过。

这样我们就可以保证，所有存入的数都是尽可能对答案有帮助的。因为假如一个数不能整除 $k$ ，必然不可能对答案造成影响。

在 $a[i]$ 与已有的数来更新新的数时，应该将所有的修改都保存起来，等到更新完了之后再应用更新。什么意思呢？假如读入了一个数 $3$ ，之前已经有了 ${2,6,18}$ 这三个数，且构成这三个数的方案数分别为 ${1,2,3}$ 。由我们的推算可知，加入 $3$ 后，可以由 $2*3$ 来使构成 $6$ 的方案数加 $1$ ，由 $6*3$ 使构成 $18$ 的方案数加 $1$ ，由 $18*3$ 使构成 $54$ 的方案数加 $1$ 。加上 $3$ 本身，处理之后的已有数字和方案数分别为： ${2,3,6,18,54}$ 和 ${1,1,3,4,1}$ 。但是如果我们边处理边更新，会导致同一个 $3$ 被重复计算。给 $6$ 的方案数加1后，新增的这个已经用过 $3$ 的方案，又与 $3$ 一起更新了 $18$ 的答案。所以应该把每次要修改的操作保存起来，把所有的待更新数更新完毕后，再应用修改到方案数组中。

由于 $k$ 较大，可能出现的数字不定，所以可以通过 $STL map$ 来作为数组。

时间复杂度大概是 $O(n log k)$ 。

#include<cstdio>
#include<map>
using std::map;
const long long maxn=1e3;
const long long mod=1000000007;
long long n,k;
long long a[maxn+5];
map<long long,long long>d;
map<long long,bool> ment;
long long mentd[maxn+5];
struct addo{
    long long to,val;
    addo(long long to=0,long long val=0):to(to),val(val){}
}add[maxn+5];
inline void read(long long &x){
    x=0;char c;long long f=1;
    do{c=getchar();if(c=='-')f=-1;}while(c>'9'||c<'0');
    do{x=x*10+c-'0';c=getchar();}while(c>='0'&&c<='9');x*=f;
}
void work(){
    for(register long long i=1;i<=n;++i){
        read(a[i]);
        if(k%a[i]!=0)continue;
        long long lmentd=mentd[0],tadd=0;
        for(register long long j=1,y;j<=lmentd;++j){
            if(k%(y=a[i]*mentd[j])!=0)continue;
            add[++tadd]=addo(y,d[mentd[j]]);
            if(!ment[y]){
                mentd[++mentd[0]]=y;
                ment[y]=true;
            }
        }
        for(register long long j=1;j<=tadd;++j){
            d[add[j].to]+=add[j].val;
            d[add[j].to]%=mod;
        }
        d[a[i]]++;
        d[a[i]]%=mod;
        if(!ment[a[i]]){
            mentd[++mentd[0]]=a[i];
            ment[a[i]]=true;
        }
    }
    printf("%lld\n",d[k]);
}
int main(){
    long long T;
    read(T);
    while(T--){
        read(n);read(k);
        work();
        if(T){
           ment.clear();
           mentd[0]=0;
        }
    }
    return 0;
}

整数划分

将N分为若干个不同整数的和，有多少种不同的划分方式，例如：n = 6，{6} {1,5} {2,4} {1,2,3}，共4种。由于数据较大，输出Mod 10^9 + 7的结果即可。
$1 \leq N \leq 50000$

当成一个0/1背包问题， $1$ 到 $N$ 每个数是一件物品，背包的容积为 $N$ 。把普通背包（求最大价值）改为求价值之和即可。

但是这种做法的时间复杂度为 $O(N^2)$ ，很显然过不了此题的数据范围。

考虑用 $g[i][j]$ 表示考虑用 $i$ 个数构成 $j$ 的方案数。要求用的数各不相同，所以应该保证构造的数不出现重复。

用 $g[i][j]$ 表示用 $j$ 个数构成i的方案数，由于每个数各不相同，最多的数的个数 $m$ 满足 $(1+2+...+m=n)$ 。计算得知 $m_{max}=316$ 。

用 $i$ 个数字来组成 $j$ ，假如不选择数字 $1$ ，那么方案数为 $g[i][j-i]$ ，也就是把构成 $j-i$ 的 $i$ 个数每个都加上 $1$ ；假如要选择数字 $1$ ，为了保证前面没有数字 $1$ （题目要求所有数不相同），我们需要把前面 $i-1$ 个数加上1，再给最后一位放一个 $1$ 。方案数就是 $g[i-1][j-i]$ （前 $i-1$ 位构成 $j-i$ ）。

选择 $1$ 和不选择 $1$ ，包含了所有的情况。

于是我们得到状态转移方程：

$g[i][j]=g[i-1][j-i]+g[i][j-i].$

答案就是 $\sum_{i=1}^{316} g[i][n].$

代码：

#include<cstdio>
#include<cmath>
const long long mod=1e9+7;
const long long maxn=5e4;
long long g[320][maxn+5];
long long ans;
long long n,m;
int main(){
    scanf("%lld",&n);
    g[0][0]=1;
    for(register int i=1;i<=319;++i){
        for(register int j=i;j<=n;++j){
            g[i][j]=(g[i][j-i]+g[i-1][j-i])%mod;
        }
    }
    for(register int i=1;i<=319;++i){
        ans+=g[i][n];
        ans%=mod;
    }
    printf("%lld\n",ans);
    return 0;
}

Everyone will be famous for fifteen minutes.

求解差分约束系统

差分约束系统是一个N元一次不等式组，由多组形如 $x_i-x_j \leqslant c_k$ 的不等式组成。一个差分约束系统要么无解，要么有无数组解。

Part 1 前置技能

在了解如何判断一个差分约束系统是否有解，或者求出它的一组解之前，我们需要先掌握它的前置技能。

图论基本概念
求单源最短/长路的方法

讲解图论的算法书籍都会讲解单源最短路的求法。在边权非负时，我们通常使用 Dijkstra 算法或 Bellman-Ford算法（以及它们的堆/队列优化算法）。Dijkstra算法不能处理负权存在时的情况，也不能求出单源最长路。Bellman-Ford算法及其队列优化的SPFA算法可以处理边带负权的情况，于是可以通过将边权取相反数的方法求出单源最长路。（见这里）Bellman-Ford算法及其队列优化的SPFA算法都可以判断图中是否存在负环，并且会在 $d[x]>d[y]+w(y,x)$ 时用 $y$ 点更新 $d[x]$ 。

在单源最短路算法结束后，假如图 $G(V,E)$ 中没有负环，那么必有：

$\forall i,j \in V , d[i] \leqslant d[j]+w(j,i)$

在你搞清楚上面两种SSSP问题求解的算法之后，我们就可以通过以下方式判断负环：

对于Bellman-Ford算法：

每次操作后，总会有一个点收敛。如果没有负环，经过 $n-1$ 轮迭代后必然不会再有点的路径长度被更新。如果迭代 $n-1$ 轮后仍然有点的距离可以被更新，那么说明一定有负环。

对于SPFA算法：

假如在用算法进行处理时，一个点的最短路径经过的边数已经大于 $n-1$ （即必然重复走了很多边和点），那么说明一定有些点可被重复走过，且重复经过这些点之后可以使距离更小。也就是说，图里有负环。使用一个数组 $cnt[]$ 记录每个点当前所求最短路经过了多少边就可以解决这个问题。方法是在用 $x$ 更新 $y$ 时，令 $cnt[y]=cnt[x]+1$ ，并判断是否 $cnt[y] > n-1$ 。

Part 2 求解差分约束系统

在理解Part 1的内容后，我们就可以用它来求解差分约束系统了。

如前所述，差分约束系统中的不等式形式是：

$x_i-x_j \leqslant c_k$

(例如 $x_2 - x_1 \leqslant 6$ )

而一个没有负环的图在跑完单源最短路算法后，满足：

$\forall i,j \in V , d[i] \leqslant d[j]+w(j,i)$

那么我们能否利用这个形式上的共同性来将求解差分约束系统的问题转化为图上的问题，然后利用图论算法求解？

当然可以。设有图 $G(V,E)$ ，对于差分约束系统中的每组关系 $x_i-x_j \leqslant c_k(i,j \in V)$ ，我们从 $j$ 点向 $i$ 点连接一条权值为 $c_k$ 的有向边。

假如从这个图的某点出发的单源最短路径为 $d[i](i \in V)$ ，满足 $\forall i,j \in V , d[i] \leqslant d[j]+w(j,i)$ ，那么这个差分约束系统必然是有解的， $d[i]$ 就是其中一组解。如果有一组解 $\{ x_1,x_2,...,x_n \}$ ，那么 $\{ x_1+k,x_2+k,...,x_n+k \} (k \in \mathbb{R} )$ 也必然是一组解。即它有无数组解。