点击访问

题面

给定两个地方v1，v2，计算在t1到t2天（包括t1,t2）内从v1到v2共有多少种走法（每条道路走需要花一天的时间，且不能在某个城市停留,且$t_1=0$时的走法数为$0$)。城市的总数<=30,两个城市间可以有多条道路，每条都视为是不同的。

代码

#include 
#include 
#include 
const int mod = 2008;
const int maxn = 210;
using namespace std;
struct matrix {
    int f[31][31];
};
matrix p[10001];
map< int, int > mp;
matrix mul( matrix a, matrix b, int n ) {
    matrix c;
    memset( c.f, 0, sizeof( c.f ) );
    for ( int i = 0; i < n; i++ ) {
        for ( int j = 0; j < n; j++ ) {
            for ( int k = 0; k < n; k++ )
                c.f[i][j] += a.f[i][k] * b.f[k][j];
            c.f[i][j] %= mod;
        }
    }
    return c;
}
matrix pow_mod( matrix a, int b, int n ) {
    matrix s;
    memset( s.f, 0, sizeof( s.f ) );![1.png][1]
    for ( int i = 0; i < n; i++ )
        s.f[i][i] = 1;
    while ( b ) {
        if ( b & 1 )
            s = mul( s, a, n );
        a = mul( a, a, n );
        b >>= 1;
    }
    return s;
}
matrix Add( matrix a, matrix b, int n ) {
    matrix c;
    for ( int i = 0; i < n; i++ ) {
        for ( int j = 0; j < n; j++ ) {
            c.f[i][j] = a.f[i][j] + b.f[i][j];
            c.f[i][j] %= mod;
        }
    }
    return c;
}//模板
int main() {
    int n, m;
    while ( cin >> n ) {
        int u, v;
        int ans = 0;
        mp.clear();
        memset( p[0].f, 0, sizeof( p[0].f ) );
        for ( int i = 0; i < n; i++ ) {
            cin>>u>>v;
            if ( mp.find( u ) == mp.end() )
                mp[u] = ans++;
            if ( mp.find( v ) == mp.end() )
                mp[v] = ans++;
            p[0].f[mp[u]][mp[v]]++;//离散,使得u->ans
        }
        for ( int i = 1; i < 10001; i++ )
            p[i] = mul( p[i - 1], p[0], ans );//计算i天的走法有多少
        cin >> m;
        int t1, t2, v1, v2;
        while ( m-- ) {
            cin>>v1>>v2>>t1>>t2;
            if ( t1 > t2 )
                swap( t1, t2 );
            if ( mp.find( v1 ) == mp.end() || mp.find( v2 ) == mp.end() || t1 == 0 && t2 == 0 ) {
                cout << 0 << endl;
                continue;
            }
            int sum = 0;
            for ( int i = t1 - 1; i < t2; i++ ) {
                sum += p[i].f[mp[v1]][mp[v2]] % mod;
            }
            cout << ( sum % mod ) << endl;
        }
    }
    return 0;
}

最后修改：2023 年 08 月 27 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏