题解 - Vijos

0

月井之春 LV 3 @ 2007-10-03 16:35:21

.....My God

0

嘻嘻 LV 3 @ 2007-08-17 22:36:13

可不可以解释得再清楚一些

偶还是看不懂啊

0

hysun LV 3 @ 2007-08-02 20:37:27

这个题竟然难度为1，这可是多米诺棋盘覆盖问题哈，属于组合数学的问题，不是很容易的，当然纯粹“拿来主义”是很简单地

0

C++无敌 LV 7 @ 2007-07-31 19:23:37

难得一次AC~~纪念一下

写起也还容易,代码90几行

0

cccum LV 3 @ 2007-07-22 09:21:01

编译通过...

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

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

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

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

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：答案正确... 0ms

├ 测试数据 12：答案正确... 0ms

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 0ms

├ 测试数据 19：答案正确... 0ms

├ 测试数据 20：答案正确... 0ms

├ 测试数据 21：答案正确... 0ms

├ 测试数据 22：答案正确... 0ms

├ 测试数据 23：答案正确... 0ms

├ 测试数据 24：答案正确... 0ms

├ 测试数据 25：答案正确... 0ms

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

Accepted 有效得分：100 有效耗时：0ms

状态压缩的dp+矩阵乘法

因为每个格子不是被覆盖就是没被覆盖，状态只有0 1两种，m

0

盗帅 LV 3 @ 2007-06-23 15:46:19

不知道怎么做诶

0

fluorine LV 3 @ 2007-04-19 22:12:09

怎么dp啊？

0

inter681 LV 3 @ 2007-04-12 21:37:40

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

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

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

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

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

├ 测试数据 11：运行超时...

├ 测试数据 12：运行超时...

├ 测试数据 13：答案正确... 0ms

├ 测试数据 14：答案正确... 0ms

├ 测试数据 15：答案正确... 0ms

├ 测试数据 16：答案正确... 0ms

├ 测试数据 17：答案正确... 0ms

├ 测试数据 18：答案正确... 244ms

├ 测试数据 19：答案正确... 572ms

├ 测试数据 20：运行超时...

├ 测试数据 21：运行超时...

├ 测试数据 22：运行超时...

├ 测试数据 23：运行超时...

├ 测试数据 24：运行超时...

├ 测试数据 25：运行超时...

直接朴素DP的结果。。

如何优化？我对矩阵的应用不是很熟悉，除了基本的k3logn经典优化

0

Roland LV 3 @ 2006-10-28 17:15:59

和斐波那切有关。。（递推公式）

0

killer LV 3 @ 2006-10-27 19:47:47

压缩DP。二进制转十存储~ 麻烦呦~~ 8写了

0

zlw0310 LV 5 @ 2006-10-25 23:06:04

好苦啊,用矩阵乘写了100多行

0

Ronice LV 3 @ 2006-10-15 18:06:17

楼下的楼下的楼下，能否提供该牛人的公式

0

g201516 LV 6 @ 2006-09-22 21:15:01

我的垃圾方法....

用矩阵乘的~

0

xjliyiru LV 3 @ 2006-08-19 12:47:25

这题不是什么藐视n的大小的题目吗？另还有一种极端的做法就是推公式，JSOI就有人这么写的。。。

-1

RabbitHu LV 7 @ 2017-07-29 15:55:58

好老的题啊！下面的题解还有十年前的2333

AC代码：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int n, m, p, M;
const int WIDTH = 34;
struct matrix {
    ll g[WIDTH][WIDTH];
    matrix(){
        memset(g, 0, sizeof(g));
    }
    matrix(int x){
        memset(g, 0, sizeof(g));
        for(int i = 0; i < M; i++)
            g[i][i] = 1;
    }
    matrix operator * (matrix b){
        matrix c;
        for(int k = 0; k < M; k++)
            for(int i = 0; i < M; i++)
                for(int j = 0; j < M; j++)
                    c.g[i][j] = (c.g[i][j] + g[i][k] * b.g[k][j] % p) % p;
        return c;
    }
} mp;
matrix qpow(matrix a, int x){
    matrix ans(1);
    while(x){
        if(x & 1) ans = ans * a;
        a = a * a;
        x >>= 1; 
    }
    return ans;
}
// Matrix67 的神奇位运算我找不到了 -_-|||
//自己编了一个十分naive的暴力判断，也能用 
bool getbit(int num, int x){
    return num & (1 << x);
}
void init(){
    for(int i = 0; i < M; i++)
        for(int j = 0; j < M; j++){
            int ok = 1, rem = j;
            for(int k = 0; k < m; k++){
                if(!getbit(i, k)){//如果母串该位为0 
                    if(!getbit(rem, k)) ok = 0;//则子串该位必为1 
                    else rem -= (1 << k);//去掉这些横放造成的突起 
                }
            }//去掉横放突起后，剩下的都是竖放的 
            int cnt = 0;
            for(int k = 0; k < m; k++){
                if(getbit(rem, k)) cnt++;//数数竖放挨在一起的有多少 
                if(!getbit(rem, k)){
                    if(cnt & 1) ok = 0;
                    cnt = 0;
                }
            }
            if(cnt & 1) ok = 0;
            if(ok) mp.g[i][j] = 1;
        }
}
int main(){
    scanf("%d%d%d", &n, &m, &p);
    M = 1 << m ;
    init();
    mp = qpow(mp, n);
    printf("%lld\n", mp.g[M - 1][M - 1]);
    return 0;
}

-1

!TNT! LV 8 @ 2017-07-01 11:16:53

纯DP方法，可以76分

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int ag[8]={0,3,6,12,15,24,27,30}; 
int f[10000010][32];
int n,m,p,w[10025][2],cnt=0;
bool pass(int a,int b){
    for(int i=0;i<8;++i) if((a&b)==ag[i]) return 1;
    return 0;
}
int main(){
    scanf("%d%d%d",&n,&m,&p);
    for(int i=0;i<(1<<m);++i)
        for(int j=0;j<(1<<m);++j)
            if((~i&j)==(~i&((1<<m)-1))&&pass(i,j)) w[cnt][0]=i,w[cnt++][1]=j;
    f[0][(1<<m)-1]=1;
    for(int i=1;i<=n;++i)
        for(int j=0;j<cnt;++j)
            f[i][w[j][1]]=(f[i][w[j][1]]+f[i-1][w[j][0]])%p;
    printf("%d\n",f[n][(1<<m)-1]%p);
}

-1

WKA LV 8 @ 2016-11-14 17:07:49

ac 50留念！膜拜matrix67神牛

-1

lemontree712 LV 10 @ 2013-09-22 21:10:32

#include <stdio.h>
int main (){
printf ("0");
return 0;
}测试数据 #0: WrongAnswer, time = 0 ms, mem = 540 KiB, score = 0

测试数据 #1: Accepted, time = 0 ms, mem = 540 KiB, score = 4

测试数据 #2: WrongAnswer, time = 0 ms, mem = 536 KiB, score = 0

测试数据 #3: WrongAnswer, time = 0 ms, mem = 532 KiB, score = 0

测试数据 #4: WrongAnswer, time = 0 ms, mem = 540 KiB, score = 0

测试数据 #5: WrongAnswer, time = 0 ms, mem = 540 KiB, score = 0

测试数据 #6: WrongAnswer, time = 0 ms, mem = 532 KiB, score = 0

测试数据 #7: Accepted, time = 15 ms, mem = 540 KiB, score = 4

测试数据 #8: WrongAnswer, time = 0 ms, mem = 540 KiB, score = 0

测试数据 #9: WrongAnswer, time = 15 ms, mem = 540 KiB, score = 0

测试数据 #10: WrongAnswer, time = 0 ms, mem = 536 KiB, score = 0

测试数据 #11: WrongAnswer, time = 0 ms, mem = 536 KiB, score = 0

测试数据 #12: WrongAnswer, time = 0 ms, mem = 544 KiB, score = 0

测试数据 #13: WrongAnswer, time = 0 ms, mem = 544 KiB, score = 0

测试数据 #14: WrongAnswer, time = 0 ms, mem = 544 KiB, score = 0

测试数据 #15: WrongAnswer, time = 0 ms, mem = 540 KiB, score = 0

测试数据 #16: WrongAnswer, time = 0 ms, mem = 540 KiB, score = 0

测试数据 #17: WrongAnswer, time = 0 ms, mem = 540 KiB, score = 0

测试数据 #18: WrongAnswer, time = 0 ms, mem = 532 KiB, score = 0

测试数据 #19: WrongAnswer, time = 0 ms, mem = 540 KiB, score = 0

测试数据 #20: WrongAnswer, time = 0 ms, mem = 540 KiB, score = 0

测试数据 #21: WrongAnswer, time = 0 ms, mem = 540 KiB, score = 0

测试数据 #22: WrongAnswer, time = 0 ms, mem = 532 KiB, score = 0

测试数据 #23: WrongAnswer, time = 0 ms, mem = 540 KiB, score = 0

测试数据 #24: WrongAnswer, time = 15 ms, mem = 540 KiB, score = 0

WrongAnswer, time = 45 ms, mem = 544 KiB, score = 8

-1

lemontree712 LV 10 @ 2013-09-22 21:08:11

#include <stdio.h>
int main (){
printf ("1");
return 0;
}测试数据 #0: Accepted, time = 0 ms, mem = 540 KiB, score = 4

测试数据 #1: WrongAnswer, time = 0 ms, mem = 540 KiB, score = 0

测试数据 #2: WrongAnswer, time = 0 ms, mem = 540 KiB, score = 0

测试数据 #3: WrongAnswer, time = 15 ms, mem = 540 KiB, score = 0

测试数据 #4: WrongAnswer, time = 0 ms, mem = 536 KiB, score = 0

测试数据 #5: WrongAnswer, time = 0 ms, mem = 536 KiB, score = 0

测试数据 #6: WrongAnswer, time = 0 ms, mem = 536 KiB, score = 0

测试数据 #7: WrongAnswer, time = 15 ms, mem = 540 KiB, score = 0

测试数据 #8: WrongAnswer, time = 0 ms, mem = 536 KiB, score = 0

测试数据 #9: WrongAnswer, time = 0 ms, mem = 540 KiB, score = 0

测试数据 #10: WrongAnswer, time = 0 ms, mem = 536 KiB, score = 0

测试数据 #11: WrongAnswer, time = 15 ms, mem = 536 KiB, score = 0

测试数据 #12: WrongAnswer, time = 0 ms, mem = 540 KiB, score = 0

测试数据 #13: WrongAnswer, time = 0 ms, mem = 540 KiB, score = 0

测试数据 #14: WrongAnswer, time = 0 ms, mem = 540 KiB, score = 0

测试数据 #15: WrongAnswer, time = 0 ms, mem = 536 KiB, score = 0

测试数据 #16: WrongAnswer, time = 15 ms, mem = 540 KiB, score = 0

测试数据 #17: WrongAnswer, time = 0 ms, mem = 536 KiB, score = 0

测试数据 #18: WrongAnswer, time = 0 ms, mem = 532 KiB, score = 0

测试数据 #19: WrongAnswer, time = 0 ms, mem = 540 KiB, score = 0

测试数据 #20: WrongAnswer, time = 0 ms, mem = 536 KiB, score = 0

测试数据 #21: WrongAnswer, time = 0 ms, mem = 536 KiB, score = 0

测试数据 #22: WrongAnswer, time = 3 ms, mem = 540 KiB, score = 0

测试数据 #23: WrongAnswer, time = 0 ms, mem = 536 KiB, score = 0

测试数据 #24: WrongAnswer, time = 0 ms, mem = 536 KiB, score = 0

WrongAnswer, time = 63 ms, mem = 540 KiB, score = 4

-1

613 LV 7 @ 2013-08-13 10:49:21

555555555555555555555

题解

66 条题解

Domino

信息

状态

开发

支持

题解

66 条题解

Domino

信息

状态

开发

支持

还没有账户？

登录