BZOJ4887 Tjoi2017可乐（动态规划+矩阵快速幂）

时间：2024-07-16 18:03:44

　　设f[i][j]为第i天到达j号城市的方案数，转移显然，答案即为每天在每个点的方案数之和。矩乘一发即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 33

#define M 110

#define P 2017

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,m,k;

struct matrix

{

    int n,a[N][N];

    matrix operator *(const matrix&b) const

    {

        matrix c;c.n=n;memset(c.a,,sizeof(c.a));

        for (int i=;i<n;i++)

            for (int j=;j<b.n;j++)

                for (int k=;k<b.n;k++)

                c.a[i][j]=(c.a[i][j]+a[i][k]*b.a[k][j])%P;

        return c;

    }

}f,v;

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj4887.in","r",stdin);

    freopen("bzoj4887.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read();

    v.n=n+;

    for (int i=;i<=m;i++)

    {

        int x=read(),y=read();

        v.a[x][y]=v.a[y][x]=;

    }

    for (int i=;i<=n;i++) v.a[i][i]=v.a[i][]=;

    k=read()+;

    f.n=;f.a[][]=;

    for (;k;k>>=,v=v*v) if (k&) f=f*v;

    cout<<f.a[][];

    return ;

}

相关文章