Submission #289361

#	Time	Username	Problem	Language	Result	Execution time	Memory
289361		limabeans	Space Pirate (JOI14_space_pirate)	C++17	0 / 100	2082 ms	524288 KiB

space_pirate

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9+7;
const int maxn = 1e6 + 5;

using matrix = vector<vector<ll>>;

void add(ll& x, ll y) {
    if (x>=mod) x%=mod;
    if (y>=mod) y%=mod;
    x += y;
    if (x>=mod) x%=mod;
}

void mul(ll& x, ll y) {
    if (x>=mod) x%=mod;
    if (y>=mod) y%=mod;
    x *= y;
    if (x>=mod) x%=mod;
}


matrix mul(matrix a, matrix b) {
    int n = a.size();
    assert(n>0);
    int m = a[0].size();
    assert(m == int(b.size()));
    int p = b[0].size();
    matrix res(n, vector<ll>(p));
    for (int i=0; i<n; i++) {
	for (int j=0; j<p; j++) {
	    for (int k=0; k<m; k++) {
		ll cur = 1;
		mul(cur, a[i][k]);
		mul(cur, b[k][j]);
		add(res[i][j], cur);
	    }
	}
    }
    return res;    
}


matrix matpw(matrix mat, ll k) {
    int n = mat.size();
    assert(mat.size() && mat.size()==mat[0].size()); //nxn
    matrix res(n,vector<ll>(n));
    for (int i=0; i<n; i++) {
	res[i][i]=1;
    }


    while (k>0) {
	if (k%2) {
	    res=mul(res,mat);
	}
	mat=mul(mat,mat);
	k=k/2;
    }

    return res;
}

int n; ll k;
int a[maxn];

ll ways[maxn];

void solve() {
    matrix M = vector<vector<ll>>(n, vector<ll>(n));
    for (int i=0; i<n; i++) {
	M[i][a[i]]=1;
    }
 
    M = matpw(M, k);

    // for (int i=0; i<n; i++) {
    // 	for (int j=0; j<n; j++) {
    // 	    cout<<M[i][j]<<" ";
    // 	}
    // 	cout<<endl;
    // }
    // cout<<endl;
    
    matrix X = vector<vector<ll>>(n, vector<ll>(n));
    X[0][0] = 1;
    X = mul(X, M);
    int to=-1;
    for (int i=0; i<n; i++) {
	if (X[0][i]>0) {
	    assert(to==-1);
	    to=i;
	}
    }
    ways[to]++;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
    cin>>n>>k;
    for (int i=0; i<n; i++) {
	cin>>a[i];
	--a[i];
    }

    for (int i=0; i<n; i++) {
	for (int j=0; j<n; j++) {
	    //cout<<i<<": "<<j<<endl;
	    int save=a[i];
	    a[i]=j;
	    solve();
	    a[i]=save;
	    
	}
    }
    for (int i=0; i<n; i++) {
	cout<<ways[i]<<"\n";
    }
    
    
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 37
• Subtask 3: 0 / 33
• Subtask 4: 0 / 20