2015 Multi-University Training Contest 3 hdu 5318 The Goddess Of The Moon
The Goddess Of The Moon
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 943 Accepted Submission(s): 426
However, while Yi went out hunting, Fengmeng broke into his house and forced Chang'e to give up the elixir of immortality to him, but she refused to do so. Instead, Chang'e drank it and flew upwards towards the heavens, choosing the moon as residence to be nearby her beloved husband.
Yi discovered what had transpired and felt sad, so he displayed the fruits and cakes that his wife Chang'e had liked, and gave sacrifices to her. Now, let’s help Yi to the moon so that he can see his beloved wife. Imagine the earth is a point and the moon is also a point, there are n kinds of short chains in the earth, each chain is described as a number, we can also take it as a string, the quantity of each kind of chain is infinite. The only condition that a string A connect another string B is there is a suffix of A , equals a prefix of B, and the length of the suffix(prefix) must bigger than one(just make the joint more stable for security concern), Yi can connect some of the chains to make a long chain so that he can reach the moon, but before he connect the chains, he wonders that how many different long chains he can make if he choose m chains from the original chains.
Each of the test case begins with two integers n, m.
(n <= 50, m <= 1e9)
The following line contains n integer numbers describe the n kinds of chains.
All the Integers are less or equal than 1e9.
11 111 is different with 111 11
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = ;
const LL mod = ;
int n,m,d[maxn];
struct Matrix {
int m[maxn][maxn];
Matrix() {
memset(m,,sizeof m);
}
Matrix operator*(const Matrix &t) const {
Matrix ret;
for(int i = ; i < n; ++i)
for(int j = ; j < n; ++j)
for(int k = ; k < n; ++k)
ret.m[i][j] = (ret.m[i][j] + (LL)m[i][k]*t.m[k][j]%mod)%mod;
return ret;
}
}; bool check(int a,int b) {
char sa[],sb[];
sprintf(sa,"%d",d[a]);
sprintf(sb,"%d",d[b]);
for(int i = ,j; sa[i]; ++i) {
for(j = ; sb[j] && sa[i+j] && sb[j] == sa[i+j]; ++j);
if(!sa[i+j] && j > ) return true;
}
return false;
}
Matrix quickPow(Matrix b,int a) {
Matrix ret;
for(int i = ; i < n; ++i)
ret.m[i][i] = ;
while(a) {
if(a&) ret = ret*b;
a >>= ;
b = b*b;
}
return ret;
}
int main() {
int kase;
scanf("%d",&kase);
while(kase--) {
scanf("%d%d",&n,&m);
for(int i = ; i < n; ++i)
scanf("%d",d+i);
sort(d,d+n);
n = unique(d,d+n) - d;
Matrix a;
for(int i = ; i < n; ++i)
for(int j = ; j < n; ++j)
a.m[i][j] = check(i,j);
Matrix ret = quickPow(a,m-);
int ans = ;
for(int i = ; i < n; ++i)
for(int j = ; j < n; ++j)
ans = (ans + ret.m[i][j])%mod;
printf("%d\n",ans);
}
return ;
}
最新文章
- MySql: 常见错误
- JavaScript:Location
- 服务器Ubuntu16.04下连接锐捷
- git Could not read from remote repository 解决
- 素数筛 poj 2689
- python 数据类型(sequence 序列、dictionary 词典、动态类型)
- 【DWT笔记】傅里叶变换与小波变换
- 微信分组群发45028,微信分组群发has no masssend quota hint
- [SOJ]&#160;Babelfish
- 简聊iOS支付集成(支付宝和微信支付)
- 第二次项目冲刺(Beta阶段)--第七天
- css元素选择器 first-child nth-child
- Python3 实现数据读写分离设计
- CorelDraw X8 破解激活问题
- TCP/IP协议、UDP协议、 Http协议
- java 线程理解
- 动画讲解TCP的3次握手,4次挥手
- Spring Security(二十一):6.3 Advanced Web Features
- NModbus类库使用
- [转载]error while loading shared libraries的解決方法