Submission #21415

#	Time	Username	Problem	Language	Result	Execution time	Memory
21415		gs14004	비트 (kriii4_Q)	C++11	100 / 100	229 ms	2384 KiB

Q

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;

lint ipow(lint x, lint p){
	lint ret = 1, piv = x % mod;
	while(p){
		if(p&1) ret *= piv;
		piv *= piv;
		ret %= mod;
		piv %= mod;
		p >>= 1;
	}
	return ret % mod;
}

const int MAXN = 105;
struct matrix{
	lint adj[MAXN][MAXN];
	int n;
	matrix(int _n, int c){
		n = _n;
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				adj[i][j] = (i == j ? c : 0);
			}
		}
	}
	matrix operator*(const matrix &a)const{
		matrix c(n, 0);
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				for(int k=0; k<n; k++){
					c.adj[j][k] += adj[j][i] * a.adj[i][k] % mod;
					c.adj[j][k] %= mod;
				}
			}
		}
		return c;
	}
};

int n, k;
vector<lint> basis[102];
lint sol[102];

void solve(){
	for(int i=n-1; i>=0; i--){
		assert(!basis[i].empty());
		for(int j=i+1; j<n; j++){
			sol[i] += mod - sol[j] * basis[i][j] % mod;
			sol[i] %= mod;
		}
		sol[i] *= ipow(basis[i][i], mod - 2);
		sol[i] %= mod;
	}
	for(int i=0; i<n; i++) printf("%lld\n", sol[i]);
}

void insert(vector<lint> v, int x){
	bool ok = 0;
	for(int i=0; i<n; i++){
		if(v[i]){
			if(basis[i].empty()){
				basis[i] = v;
				sol[i] = x;
				ok = 1;
				break;
			}
			else{
				lint w = ipow(basis[i][i], mod - 2) * v[i] % mod;
				for(int j=0; j<n; j++){
					v[j] += mod - w * basis[i][j] % mod;
					v[j] %= mod;
				}
				x += mod - w * sol[i] % mod;
				x %= mod;
			}
		}
	}
	assert(ok);
}

int main(){
	cin >> n >> k;
	matrix ret(n+1, 1), piv(n+1, 0);
	for(int i=0; i<=n; i++){
		if(i < n) piv.adj[i][i+1] = (n - i) * ipow(n, mod-2) % mod;
		if(i > 0) piv.adj[i][i-1] = i * ipow(n, mod-2) % mod;
	}
	for(; k; k>>=1){
		if(k&1) ret = ret * piv;
		piv = piv * piv;
	}
	for(int i=0; i<n; i++){
		vector<lint> rw(n);
		rw[i]++;
		for(int j=0; j<n; j++){
			rw[j] += mod - ret.adj[i+1][j+1];
			rw[j] %= mod;
		}
		insert(rw, 1);
	}
	solve();
}

• Subtask 1: 9 / 9
• Subtask 2: 91 / 91