题解

22 条题解

  • 2
    @ 2017-11-07 18:47:08
    # pragma GCC optimize(2)
    //#include<ctime>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    int g[16][16][16][16],f[20][20][65536];
    char ch[16][16];
    int*F,*G;
    void _(int&a,int b){(a+=b)>=19901013?a-=19901013:0;}
    int main(){
        int n,m;scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)scanf("%s",ch[i]+1);//printf("%d\n",clock());
        for(int l=1;l<=m;l++)for(int r=l;r<=m;r++)for(int u=1;u<=n;u++){
            int O=1<<r-l+1;--O;
            G=f[u][l];*G=1;
            memset(G+1,0,O<<2);
            for(int i=u;i<=n;//printf("g[%d][%d][%d][%d]=%d\n",u,i,l,r,g[u][i][l][r]),
            i++)for(int j=l;j<=r;j++){
                F=G;G=j==r?f[i+1][l]:f[i][j+1];
                memset(G,0,(O<<2)+4);
                int x=1<<r-j,c1=ch[i][j],c2=ch[i][j-1],c3=ch[i-1][j];
                for(int k=0,*Fk=F;k<=O;k++,Fk++){
                    if(!*Fk)continue;
                    _(G[k&~(x)],*Fk);
                    if(j>l&&c2&2&&c1&2&&!(k&(x+x)))_(G[k|(x+x+x)],*Fk);
                    if(i>u&&c3&2&&c1&2&&!(k&(x)))_(G[k|(x)],*Fk);
                }if(j==r)for(int k=0,*Gk=G;k<=O;k++,Gk++)_(g[u][i][l][r],*Gk);
                //for(int k=0;k<=O;k++)G[k]=0;
                //for(int k=0;k<=O;k++)printf("G[%d]=%d F[%d]=%d i=%d j=%d\n",k,G[k],k,F[k],i,j);
            }
        }//printf("%d,%d\n",g[1][n][1][m],clock());puts("");
        long long ans=0,tmp=0,g[16]={0};
        for(int i=0;i<(1<<m);i+=2){
            int t=0,o[16];
            o[0]=0;
            for(int j=1;j<m;j++)if(i&(1<<j))o[++t]=j;
            o[++t]=m;
            for(int d=1;d<=n;d++)for(int u=1;u<=d;u++){
                tmp=1;
                for(int i=1;i<=t;i++)tmp=tmp*::g[u][d][o[i-1]+1][o[i]]%19901013;
                if(u==1)g[d]=tmp;else g[d]=(g[d]+(19901013-tmp)*g[u-1])%19901013;
            }ans+=t&1?g[n]:19901013-g[n];if(ans>19901012)ans-=19901013;
        }printf("%d\n",(int)ans);
    }
    

    绝对良心

  • 0
    @ 2009-11-03 19:13:34

    暴力DP只能拿70分。。。查了报告。。用容斥原理才能搞定。。。

  • 0
    @ 2009-10-04 12:05:12

    没有希望了,太变态了

  • 0
    @ 2009-09-19 15:48:16

    jiayou

  • 0
    @ 2009-08-21 16:19:44

    这是一道天牛题,不是我能做的....

    观望天牛AC吧....

  • 0
    @ 2009-08-15 19:12:40

    这题是YHC天牛出的,是今年浙江省选最后一题,做出来的应该一部分是标程

  • 0
    @ 2009-07-31 20:49:23

    我也不会.

  • 0
    @ 2009-07-23 13:51:40

    不会......标程太长了......

  • 0
    @ 2009-07-21 17:35:47

    貌似 状态压缩dp+容斥原理

  • 0
    @ 2009-07-21 00:01:27

    只有80分捏。。不是7秒么

  • 0
    @ 2009-07-20 19:48:55

    Orz..

  • 0
    @ 2009-07-21 08:04:54

    Orz,太牛×了,不会做。

  • 0
    @ 2009-07-20 18:53:58

    虽然提交题目的人很牛,能过7个点...

    不过VJ不是要交标程能过才能放题吗

  • 0
    @ 2009-07-22 11:00:46

    看了xys的题解……太难了。。

  • 0
    @ 2009-07-20 14:23:57

    回楼下,那个twb是假的,他是宋神牛!!!!!!!!!

  • 0
    @ 2009-07-20 13:38:46

    下面的TWB神牛说说我也会,你过了吗?怎一个B字了得,我看你是假冒的吧,真正的twb神牛应该很modest

  • 0
    @ 2009-07-20 12:37:34

    很好玩哦~

    打表吧~

    ---|闪---|

  • 0
    @ 2009-07-20 14:34:55

    楼下的楼下的楼下的楼下是假的。

  • 0
    @ 2009-07-21 08:23:30

    都是标程

  • 0
    @ 2010-03-05 17:56:46

    囧rz,我写出来的程序虽然只有2.3KB,但是巨慢:

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 290ms

    ├ 测试数据 06:答案正确... 727ms

    ├ 测试数据 07:答案正确... 306ms

    ├ 测试数据 08:答案正确... 1210ms

    ├ 测试数据 09:答案正确... 1897ms

    ├ 测试数据 10:答案正确... 4408ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:8838ms

信息

ID
1581
难度
7
分类
动态规划 | 状态压缩DP 点击显示
标签
递交数
219
已通过
43
通过率
20%
被复制
1
上传者