HDU 5411 CRB and puzzle (Dp + 矩阵高速幂)
CRB and Puzzle
Time Limit: 2000/1000 MS (Java/Others) Memory
Limit: 65536/65536 K (Java/Others)
Total Submission(s): 483 Accepted Submission(s): 198
There are kinds
of pieces with infinite supply.
He can assemble one piece to the right side of the previously assembled one.
For each kind of pieces, only restricted kinds can be assembled with.
How many different patterns he can assemble with at most pieces?
(Two patterns and are
considered different if their lengths are different or there exists an integer such
that -th
piece of
rev=2.4-beta-2" alt="" style=""> is
different from corresponding piece of .)
rev=2.4-beta-2" alt="" style="">,
indicating the number of test cases. For each test case:
The first line contains two integers
rev=2.4-beta-2" alt="" style="">, denoting
the number of kinds of pieces and the maximum number of moves.
Then lines
follow. -th
line is described as following format.
k
rev=2.4-beta-2" alt="" style="">
rev=2.4-beta-2" alt="" style="">
rev=2.4-beta-2" alt="" style="">
rev=2.4-beta-2" alt="" style="">
rev=2.4-beta-2" alt="" style="">
rev=2.4-beta-2" alt="" style="">
rev=2.4-beta-2" alt="" style="">
Here
rev=2.4-beta-2" alt="" style=""> is
the number of kinds which can be assembled to the right of the -th
kind. Next integers
represent each of them.
1 ≤
rev=2.4-beta-2" alt="" style=""> ≤
20
1 ≤ ≤
50
1 ≤ ≤
rev=2.4-beta-2" alt="" style="">
rev=2.4-beta-2" alt="" style="">
0 ≤ ≤
1 ≤ <
rev=2.4-beta-2" alt="" style=""> <
… < ≤
N
1
3 2
1 2
1 3
0
6Hintpossible patterns are ∅, 1, 2, 3, 1→2, 2→3
DP方程非常easy想到 dp[i][j] = sum(dp[i-1][k] <k,j>连通) 构造矩阵用矩阵高速幂加速就可以。
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#define LL long long
using namespace std;
const int MAXN = 55 + 10;
const int mod = 2015;
int n, m;
struct Matrix
{
int m[MAXN][MAXN];
Matrix(){memset(m, 0, sizeof(m));}
Matrix operator * (const Matrix &b)const
{
Matrix res;
for(int i=1;i<=n+1;i++)
{
for(int j=1;j<=n+1;j++)
{
for(int k=1;k<=n+1;k++)
{
res.m[i][j] = (res.m[i][j] + m[i][k] * b.m[k][j]) % mod;
}
}
}
return res;
}
};
Matrix pow_mod(Matrix a, int b)
{
Matrix res;
for(int i=1;i<=n+1;i++) res.m[i][i] = 1;
while(b)
{
if(b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
Matrix a, b;
scanf("%d%d", &n, &m);
for(int i=1;i<=n+1;i++) a.m[i][n+1] = 1;
for(int i=1;i<=n;i++)
{
int x, k;scanf("%d", &k);
for(;k--;)
{
scanf("%d", &x);
a.m[i][x] = 1;
}
}
a = pow_mod(a, m);
int ans = 0;
for(int i=1;i<=n+1;i++) ans = (ans + a.m[i][n+1]) % mod;
printf("%d\n", ans);
}
return 0;
}
最新文章
- 微信分享接口SDK简介使用
- 1927: [Sdoi2010]星际竞速
- Intellij Idea使用技巧、快捷键
- CVE-2013-3908 Internet Explorer打印预览功能可导致信息泄露
- Combination Sum [LeetCode]
- FreeBSD下查看各软件版本命令
- 使用devpartner的blockchecker检查c++内存错误
- Cracking the coding interview--Q1.6
- js判断是否为ie的方法
- 微型 ORM 的第一篇 DapperLambda发布
- 逆波兰表达式(RPN)算法简单实现
- CAN通讯的总结
- HashMap 之弱引用 - WeakHashMap
- MYSQL ORDER BY Optimization
- 前端开发——HTML学习笔记
- .NetCore Cap 注册 Consul 服务发现
- [leetcode]Wildcard Matching @ Python
- 【原创】Team Foundation Server 域环境迁移
- pxe前期网络准备
- 从MySQL到ORM(三):连接、存储过程和用户权限