提出 #22020766

---

ソースコード 拡げる

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
template<class T,class U> inline bool chmin(T&x,U y){if(x>y){x=y;return true;}return false;}
template<class T,class U> inline bool chmax(T&x,U y){if(x<y){x=y;return true;}return false;}

using mint = modint1000000007;

template<class T> struct mat{
    int n,m;
    std::vector<std::vector<T>> v;
    T a;
    explicit mat(int e=0):n(-1),m(-1),v(){
        if(e==0) m=0;
        if(e==1) m=1;
    }
    mat(int n,int m,T e):n(n),m(m),v(n,std::vector<T>(m)){
        for(int i{};i<(n);++i){
            if(i<m) v[i][i]=e;
        }
    }
    mat(std::vector<std::vector<T>>& v):n(v.size()),m(v[0].size()),v(std::move(v)){}
    bool operator==(const mat& x){
        if(n!=x.n||m!=x.m) return false;
        for(int i{};i<(n);++i){
            for(int j{};j<(m);++j){
                if(v[i][j]!=x.v[i][j]) return false;
            }
        }
        return true;
    }
    mat& operator=(const mat& x) = default;
    mat operator+(const mat& x){
        if(n==-1&&m==0) return x;
        if(x.n==-1&&x.m==0) return *this;
        assert(n==x.n and m==x.m);
        auto y=std::vector(n,std::vector<T>(m));
        for(int i{};i<(n);++i){
            for(int j{};j<(m);++j){
                y[i][j]=v[i][j]+x.v[i][j];
            }
        }
        return mat(y);
    }
    mat operator-(const mat& x){
        if(n==-1&&m==0){
            auto y=std::vector(x.n,std::vector<T>(x.m));
            for(int i{};i<(x.n);++i){
                for(int j{};j<(x.m);++j){
                    y[i][j]=T()-x.v[i][j];
                }
            }
            return mat(y);
        }
        if(x.n==-1&&x.m==0) return *this;
        if(n!=x.n||m!=x.m) return mat();
        auto y=std::vector(x.n,std::vector<T>(x.m));
        for(int i{};i<(x.n);++i){
            for(int j{};j<(x.m);++j){
                y[i][j]=v[i][j]-x.v[i][j];
            }
        }
        return mat(y);
    }
    mat operator*(const mat& x){
        if(n==-1&&m==1) return x;
        if(x.n==-1&&x.m==1) return *this;
        assert(m==x.n);
        auto y=std::vector(x.n,std::vector<T>(x.m));
        for(int i{};i<(n);++i){
            for(int k{};k<(m);++k){
                for(int j{};j<(x.m);++j){
                    y[i][j]+=v[i][k]*x.v[k][j];
                }
            }
        }
        return mat(y);
    }
    mat& operator+=(const mat& x){
        assert(n==x.n and m==x.m);
        for(int i{};i<(n);++i){
            for(int j{};j<(m);++j){
                v[i][j]+=x.v[i][j];
            }
        }
        return *this;
    }
    mat& operator-=(const mat& x){
        assert(n==x.n and m==x.m);
        for(int i{};i<(n);++i){
            for(int j{};j<(m);++j){
                v[i][j]-=x.v[i][j];
            }
        }
        return *this;
    }
    mat& operator*=(const mat& x){
        *this=*this*x;
        return *this;
    }
    T& operator()(int i,int j){
        if(n==-1){
            if(m==1&&i==j) a=T(1);
            return a;
        }
        return v[i][j];
    }
    T det(){
        if(n==0){
            if(m==0) return T();
            if(m==1) return T(1);
        }
        if(n!=m) return T();
        mat y=*this;
        int c=1;
        for(int i=0;i<n;++i){
            for(int j=i;j<n;++j){
                if(v[j][i]!=T()){
                    if(i!=j){
                        swap(v[i],v[j]);
                        c*=-1;
                    }
                    break;
                }
                if(j==n-1) return T();
            }
            for(int j=i+1;j<n;++j){
                T ka=v[j][i]/v[i][i];
                for(int k=i;k<n;k++){
                    v[j][k]-=v[i][k]*ka;
                }
            }
        }
        T d=T(1);
        for(int i=0;i<n;i++) d*=v[i][i];
        d*=c;
        *this=y;
        return d;
    }

    void print(){
        if(n<0){
            std::cout<<"("<<m<<")"<<std::endl;
            return;
        }
        for(int i{};i<(n);++i){
            for(int j{};j<(m);++j){
                std::cout<<v[i][j]<<" ";
            }
            std::cout<<std::endl;
        }
    }
};

template<class T,class U>
T pw(T n,U m){
    T ans(1),tmp(n);
    while(m){
        if(m&1) ans*=tmp;
        m>>=1;
        tmp*=tmp;
    }
    return ans;
}

void solve(){
    int n,m,k;
    cin >> n >> m>> k;
    vector<vector<mint>> a(n,vector<mint>(1));
    int tmp;
    for(auto&i:a){
        cin>>tmp;
        i[0]=tmp;
    }
    mint iv=mint(m).inv(), iv2=iv/2;
    vector<vector<mint>> e(n,vector<mint>(n));
    for(int i{},x,y;i<(m);++i){
        cin>>x>>y;
        --x,--y;
        for(int i{};i<(n);++i){
            if(i!=x and i!=y){
                e[i][i]+=iv;
            }
        }
        e[x][x]+=iv2;
        e[x][y]+=iv2;
        e[y][x]+=iv2;
        e[y][y]+=iv2;
    }
    for(auto v:(pw(mat<mint>(e),k)*mat<mint>(a)).v){
        cout<<v[0].val()<<'\n';
    }
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    solve();
}

提出情報

ジャッジ結果