首页 > 代码库 > BZOJ1297: [SCOI2009]迷路

BZOJ1297: [SCOI2009]迷路

2024-07-22 21:13:59   213人阅读

1297: [SCOI2009]迷路

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 591  Solved: 401
[Submit][Status]

Description

windy在有向图中迷路了。该有向图有 N 个节点，windy从节点 0 出发，他必须恰好在 T 时刻到达节点 N-1。现在给出该有向图，你能告诉windy总共有多少种不同的路径吗？注意：windy不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。

Input

第一行包含两个整数，N T。接下来有 N 行，每行一个长度为 N 的字符串。第i行第j列为‘0‘表示从节点i到节点j没有边。为‘1‘到‘9‘表示从节点i到节点j需要耗费的时间。

Output

包含一个整数，可能的路径数，这个数可能很大，只需输出这个数除以2009的余数。

Sample Input

【输入样例一】
2 2
11
00

【输入样例二】
5 30
12045
07105
47805
12024
12345


Sample Output

【输出样例一】
1

【样例解释一】
0->0->1

【输出样例二】
852

HINT

30%的数据，满足 2 <= N <= 5 ； 1 <= T <= 30 。
100%的数据，满足 2 <= N <= 10 ； 1 <= T <= 1000000000 。

Source

Day2

题解：

好不容易想到了正解，结果妈蛋的调了3节课。。。

结果居然是输出b写成输出a了，我是有多sb。。。这种sb错误考场上犯一个就跪了。。。
我刚开始想能不能像沼泽鳄鱼一题一样，先预处理出小范围内的，然后ksm，忽然发现总有某些情况会被忽视。
于是开始钻研数据范围：n怎么这么小，按理说矩乘的范围都是上百的啊？距离怎么也这么小？唉？n*距离好像差不多？对了，拆点！
一想到拆点这题瞬间变水题。。。
代码：
 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm>                                                                          6 #include<iostream>                                                                              7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 100+10014 #define maxm 100+10015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define mod 200923 #define num(x,y) 10*(x-1)+(y)24 using namespace std;25 inline ll read()26 {27     ll x=0,f=1;char ch=getchar();28     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}29     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}30     return x*f;31 }32 struct matrix33 {34     int d[maxn][maxn];35     matrix(){memset(d,0,sizeof(d));}36 }a,b;37 ll n,m,tot;38 string s;39 matrix operator *(matrix &x,matrix &y)40 {41     matrix t;42     for1(i,tot)43      for1(j,tot)44       for1(k,tot)45        t.d[i][j]=(t.d[i][j]+x.d[i][k]*y.d[k][j])%mod;46     return t;47 }48 void ksm(ll cs)49 {50     for(;cs;cs>>=1,a=a*a)51         if(cs&1)b=b*a;52 }53 int main()54 {55     freopen("input.txt","r",stdin);56     freopen("output.txt","w",stdout);57     n=read();m=read();tot=10*n+9;58     for1(i,n)for1(j,8)a.d[num(i,j)][num(i,j+1)]=1;59     for1(i,n)60      { 61          cin>>s;62          for0(j,n-1)if(s[j]!=‘0‘)a.d[num(i,s[j]-‘0‘)][num(j+1,1)]=1;63      } 64     for1(i,tot)b.d[i][i]=1;65     ksm(m);                          66     printf("%d\n",b.d[num(1,1)][num(n,1)]); 67     return 0;68 }
View Code

 


BZOJ1297: [SCOI2009]迷路


联系
我们