Processing math: 100%

BZOJ3612:[Heoi2014]平衡 整数划分

10 年前

思路:

首先有两种情况,就是在中轴线处放不放,于是问题转化为在两侧分别放一些橡皮,使得距离之和相同.

我们令f[i][j]表示在一侧放橡皮,距离之和为i,共放了j个橡皮的可行方案数.

不难转化为整数分解问题,也就是将整数i分解为j个不相同正整数,且每个正整数均不超过n的问题.

我们依旧分情况讨论:

[1]若划分的最小正整数为1,我们拿走最下面一行,转化为f[i−j][j−1].

[2]否则,我们拿走最下面一行转化为f[i−j][j].

不过最大的正整数不能超过n,我们发现我们每次都是在最下面加上一行,那么如果加上后不合法,最后一列就应该是n+1,于是不合法的方案数就应该是f[i−n−1][j−1].

于是f[i][j]=f[i−j][j]+f[i−j][j−1]−f[i−n−1][j−1]

记忆化搜索水过.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
  
int n,k,p,lim;
  
int f[100010][11];
  
int Solve(int i,int j){
    if(j==1)return(i>0&&i<=n)?1:0;
    if(i<=0||i<(1+j)*j/2||i>=j*n)return 0;
    if(f[i][j]!=-1)return f[i][j];
    return f[i][j]=((long long)Solve(i-j,j-1)+Solve(i-j,j)-Solve(i-n-1,j-1)+p)%p;
}
int main(){
    int T;cin>>T;
    register int i,j;
    while(T--){
        scanf("%d%d%d",&n,&k,&p);
        if(k==1){puts("1");continue;}
        memset(f,-1,sizeof f);
        for(i=0;i<=n*k;++i)f[i][0]=0;
        for(i=1;i<=n*k;++i)for(j=1;j<=k;++j)f[i][j]=Solve(i,j);//printf("n=%d m=%d t=%d\n",i,j,f[i][j]);
        long long res=0;
        for(i=1;i<=n*k;++i){
            for(j=1;j<k;++j){
                res=(res+(long long)f[i][j]*f[i][k-j])%p;
                res=(res+(long long)f[i][j]*f[i][k-j-1])%p;
            }
        }
        printf("%d\n",res);
    }return 0;
}

Tags: 整数划分
Posted in BZOJ | 0 Comments

BZOJ2476:战场的数目 矩阵乘法+整数划分

10 年前

思路:

首先注意到不允许出现矩形,而这个条件很难限制,不过我们可以将矩形也一起算进去,在最后减掉,因为矩形的数目是可以O(1)计算的.

接下来就是考虑令fi表示周长为i的合法方案数.

我们考虑几种情况:

[1]左侧有一个高度为1的方块

[2]右侧有一个高度为1的方块

[3]左右两侧均没有一个高度为1的方块

对于[1][2],我们可以分别在左侧和右侧拿走一个方块使得周长减少2,对于[3],我们可以拿走下面的一层使得周长减少2.不难发现这些关系都是一一对应的.

下面考虑一个问题,如果一种形态是两侧均有一个方块,那么我们事实上是算了两遍的.所以我们需要减去这种情况.而显然这种情况与周长减少了4的情况一一对应.

因此我们有:fi=3fi−2−fi−4

利用矩阵乘法即可.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
  
typedef long long LL;
static const int mod=987654321;
struct Matrix{
    int w,h;LL d[2][2];
    Matrix(int _w,int _h):w(_w),h(_h){memset(d,0,sizeof d);}
    inline void operator*=(const Matrix&B){
        Matrix C(w,B.h);
        register int i,j,k;
        for(i=0;i<C.w;++i)
            for(j=0;j<C.h;++j)
                for(k=0;k<h;++k)
                    C.d[i][j]=(C.d[i][j]+d[i][k]*B.d[k][j])%mod;
        *this=C;
    }
};
  
int main(){
    int n;
    while(scanf("%d",&n)&&n){
        if(n<=3||n&1){puts("0");continue;}
        int t=n/2-1,res;
        if(t==1)res=1;else if(t==2)res=2;
        else{
            Matrix ans(1,2);ans.d[0][0]=1,ans.d[0][1]=2;
            Matrix add(2,2);add.d[0][0]=0,add.d[0][1]=-1,add.d[1][0]=1,add.d[1][1]=3;
            Matrix one(2,2);one.d[0][0]=one.d[1][1]=1;
            t-=2;for(;t;t>>=1,add*=add)if(t&1)one*=add;
            ans*=one;
            res=ans.d[0][1];
        }
        res=((LL)res-(n/2-1)+mod)%mod;
        printf("%d\n",res);
    }return 0;
}

Tags: 整数划分 矩阵乘法
Posted in BZOJ | 0 Comments