Submission #1395603

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

#define int long long
#define MOD 1000000007
#define cerr if(0)cerr

#define rep(i, n) for (int i = 0; i < (n); i++)
#define itrep(i, a) for (auto i = (a).begin(); i != (a).end(); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()

using namespace std;

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, -1, 0, 1 };

template<class T> void inputVector(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < v.size(); i++) cin >> v[i];
}

class ModInt {
private:
    long long value;
    long long mod;

    long long calcModNum(long long value) {
	if (value < 0) {
	    long long times = (-value) / this->mod + 1;
	    value += this->mod * times;
	}
	return value % this->mod;
    }

    long long extgcd(long long a, long long b, long long &x, long long &y) {
	long long g = a;
	x = 1;
	y = 0;
	if (b != 0) {
	    g = extgcd(b, a % b, y, x);
	    y -= (a / b) * x;
	}
	return g;
    }

    long long modInverse(long long a, long long b) {
	long long x, y;
	extgcd(a, b, x, y);
	return x;
    }
public:
    // コンストラクタ
    ModInt(int value, int mod) {
	this->value = (long long)value;
	this->mod = (long long)mod;
    }

    // 値を返す
    int getValue() {
	return (int)this->value;
    }

    ModInt operator + (ModInt obj) {
	ModInt retObj(calcModNum(this->value + obj.value), this->mod);
	return retObj;
    }
    void operator += (ModInt obj) {
	this->value = calcModNum(this->value + obj.value);
    }
    ModInt operator + (int value) {
	ModInt retObj(calcModNum(this->value + (long long)value), this->mod);
	return retObj;
    }
    void operator += (int value) {
	this->value = calcModNum(this->value + (long long)value);
    }

    ModInt operator - (ModInt obj) {
	ModInt retObj(calcModNum(this->value - obj.value), this->mod);
	return retObj;
    }
    void operator -= (ModInt obj) {
	this->value = calcModNum(this->value - obj.value);
    }
    ModInt operator - (int value) {
	ModInt retObj(calcModNum(this->value - (long long)value), this->mod);
	return retObj;
    }
    void operator -= (int value) {
	this->value = calcModNum(this->value - (long long)value);
    }

    ModInt operator * (ModInt obj) {
	ModInt retObj(calcModNum(this->value * obj.value), this->mod);
	return retObj;
    }
    void operator *= (ModInt obj) {
	this->value = calcModNum(this->value * obj.value);
    }
    ModInt operator * (int value) {
	ModInt retObj(calcModNum(this->value * (long long)value), this->mod);
	return retObj;
    }
    void operator *= (int value) {
	this->value = calcModNum(this->value * (long long)value);
    }

    ModInt operator / (ModInt obj) {
	ModInt retObj(calcModNum(this->value * modInverse(obj.value, this->mod)), this->mod);
	return retObj;
    }
    void operator /= (ModInt obj) {
	this->value = calcModNum(this->value * modInverse(obj.value, this->mod));
    }
    ModInt operator / (int value) {
	ModInt retObj(calcModNum(this->value * modInverse(value, this->mod)), this->mod);
	return retObj;
    }
    void operator /= (int value) {
	this->value = calcModNum(this->value * modInverse(value, this->mod));
    }
};

int cnt[100020];
int kaijo[100020];
int permN1[100020];
int permT13[100020];

int tn;
int t1, t2, t3;

int comb(int n, int r) {
	if (n == r) return 1;
	if (n == 0) return 0;
	if (n < r) return 0;
	if (r == 0) return 1;

	ModInt ret = ModInt(1, MOD);
	if (n == tn - 1) ret *= permN1[r];
	else if (n == t1 + t3) ret *= permT13[r];
	else cerr << "ERROR" << endl;
	cerr << " ->" << ret.getValue() << endl;

	ret /= kaijo[r];
	cerr << " ->" << ret.getValue() << endl;

	return ret.getValue();
}

signed main() {
	int hoge = 1;
	kaijo[0] = 1;
	REP(i, 1, 100010) {
		hoge *= i;
		hoge %= MOD;
		kaijo[i] = hoge;
	}

	int n;
	cin >> n;

	tn = n;

	vector<int> a;
	inputVector(a, n);

	int num;
	int pt1 = -1, pt2 = -1;
	rep(i, n) cnt[a[i]]++;
	rep(i, n + 10) if (cnt[i] == 2) num = i;
	rep(i, n) {
		if (a[i] != num) continue;
		if (pt1 == -1) pt1 = i;
		else pt2 = i;
	}

	t1 = pt1;
	t2 = pt2 - pt1 - 1;
	t3 = n - pt2;

	{
		int tmp = n - 1;
		int tmp2 = tmp;
		REP(i, 1, n - 1) {
			permN1[i] = tmp;
			tmp2--;
			tmp *= tmp2;
			tmp %= MOD;
		}

		tmp = t1 + t3;
		tmp2 = tmp;
		REP(i, 1, t1 + t3) {
			permT13[i] = tmp;
			tmp2--;
			tmp *= tmp2;
			tmp %= MOD;
		}
	}

	// len = 1
	cout << n << endl;

	REP(r, 2, n) {
		long long ret = 0;
		ret += comb(n - 1, r);
		cerr << "->" << ret << endl;
		//ret += comb(t1 + t2, r - 1) * 2;
		//cerr << "->" << ret << endl;
		//ret += comb(t2 + t3, r - 1);
		//cerr << "->" << ret << endl;
		//ret += comb(t1 + t3, r - 1) * 2;
		//cerr << "->" << ret << endl;
		ret += comb(n - 1, r - 1) * 2;
		cerr << "->" << ret << endl;
		ret += comb(n - 1, r - 2);
		cerr << "->" << ret << endl;

		ret -= comb(t1 + t3, r - 1);
		cerr << "->" << ret << endl;
		//ret -= comb(t2, r - 1);
		//cerr << "->" << ret << endl;
		//ret -= comb(t3, r - 1);
		//cerr << "->" << ret << endl;

		ret %= MOD;

		cout << ret << endl;
		cerr << "---" << endl;
	}

	// len = n + 1
	cout << 1 << endl;

    return 0;
}

Submission Info

Judge Result