結果

問題 No.271 next_permutation (2)
ユーザー koyumeishikoyumeishi
提出日時 2015-08-25 14:51:11
言語 C++11
(gcc 11.4.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 4,999 bytes
コンパイル時間 582 ms
コンパイル使用メモリ 81,124 KB
最終ジャッジ日時 2024-04-27 02:09:42
合計ジャッジ時間 1,435 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function ‘long long int func(std::vector<int>, int)’:
main.cpp:257:9: error: ‘iota’ was not declared in this scope
  257 |         iota(full.begin(), full.end(), 0);
      |         ^~~~

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <functional>
#include <set>
using namespace std;

template<class T = int>
class BinaryIndexedTree_1_indexed{
	void init(const vector<T> &A){
		for(int i=0; i<N; i++){
			add(i+1, A[i]);
		}
	}
	
public:
	vector<T> tree;
	int N;
	
	BinaryIndexedTree_1_indexed(const int n) : tree(n+1,0), N(n){
		
	}
	
	BinaryIndexedTree_1_indexed(const vector<T> &A) : tree(A.size()+1,0), N(A.size()){
		init(A);
	}

	//caution : position "i" must be 1-indexed
	void add(int i, const T x){
		while(i <= N){
			tree[i] += x;
			i += i & -i;
		}
	}

	//update node i to zero
	void to_zero(const int i){
		T val = get_at(i);
		add(i, -val);
	}

	//get sums [0,i]
	T get_sum(int i){
		T ret=0;
		while(i>0){
			ret += tree[i];
			i -= i & -i;
		}
		return ret;
	}

	//get sums [from,to]
	T get_sums_range(const int from, const int to){
		return get_sum(to) - get_sum(from-1);
	}

	//get at [i]
	T get_at(const int i){
		return get_sum(i) - get_sum(i-1);
	}

	int lower_bound(T val){
		if(val<=0) return 0;
		int x = 0;
		int k = 1;
		while((k<<1) <= N) k<<=1;
		
		for( ; k>0; k>>=1){
			if( x+k <= N && tree[x+k] < val ){
				val -= tree[x+k];
				x += k;
			}
		}
		return x+1;
	}

	void print(){
		for(int i=0; i<=N; i++){
			cerr << tree[i] << " ";
		}
		cerr << endl;
	}
};

class Fuctorial_Number_System{
public:
	vector<int> f;
	int size;

	Fuctorial_Number_System(){}

	Fuctorial_Number_System(vector<int>& f_){
		size = f_.size();
		f = f_;
	}

	Fuctorial_Number_System(long long x){
		long long k = 1;
		do{
			f.push_back(x%k);
			x/=k;
			k++;
		}while(x>0);

		size = f.size();
	}

	Fuctorial_Number_System operator = (Fuctorial_Number_System& x){
		f = x.f;
		size = x.size;
		return *this;
	}

	int& operator[](int pos){
		return f[pos];
	}

	Fuctorial_Number_System operator + (const Fuctorial_Number_System& x){
		vector<int> a = this->f;
		vector<int> b = x.f;
		a.resize(max(size, x.size), 0);
		b.resize(max(size, x.size), 0);
		int carry = 0;
		for(int i=0; i<a.size(); i++){
			a[i] += b[i] + carry;
			carry = 0;
			if(a[i] > i){
				carry = a[i]/(i+1);
				a[i] %= (i+1);
			}
		}
		if(carry != 0){
			a.push_back(carry);
		}
		return Fuctorial_Number_System(a);
	}
};

ostream& operator << (ostream& os, Fuctorial_Number_System& x){
	for(int i=0; i<x.size; i++){
		os << x[i] << " ";
	}
	return os;
}

#define MOD 1000000007

long long func(vector<int> p, int len){
	p.resize( max( (int)p.size(), len) +1, 0);

	int n = p.size();
	vector<long long> tmp;

	tmp = [&](){
		vector<long long> dp(2, 0);

		dp[0] = 1;
		for(int i=n-1; i>len; i--){
			vector<long long> dp_(2, 0);

			for(int b=0; b<2; b++){
				for(int d=0; d<i; d++){

					int next_b = b | (d<p[i-1]);
					if(b==0 && d>p[i-1]){
						continue;
					}

					dp_[next_b] += dp[b];
					dp_[next_b] %= MOD;

				}
			}

			swap(dp, dp_);
		}


		return dp;
	}();


	vector<long long> sum(len+1, 0);
	for(int i=1; i<=len; i++){
		sum[i] = (sum[i-1] + i) % MOD;
	}

	auto right = [&](vector<int>& my_p){

		vector<long long> dp(2, 0);
		vector<long long> cnt(2, 0);
		cnt[0] = 1;

		bool ok = false;

		for(int i=len-1; i>=0; i--){
			vector<long long> dp_(2, 0);
			vector<long long> cnt_(2, 0);

			if(my_p[i] != 0){	// 0 -> 1
				dp_[1] += dp[0] * my_p[i] % MOD + sum[my_p[i]-1] * cnt[0] % MOD;
				dp_[1] %= MOD;

				cnt_[1] += cnt[0] * my_p[i];
				cnt_[1] %= MOD;
			}
			{	// 0 -> 0
				dp_[0] += dp[0] * 1 + my_p[i] * cnt[0] % MOD;
				dp_[0] %= MOD;

				cnt_[0] += cnt[0] * 1;
				cnt_[0] %= MOD;
			}

			{	// 1 -> 1
				dp_[1] += dp[1] * (i+1) % MOD + sum[i] * cnt[1] % MOD;
				dp_[1] %= MOD;

				cnt_[1] += cnt[1] * (i+1);
				cnt_[1] %= MOD;

			}
			/*
			for(int b=0; b<2; b++){
				if(cnt[b] == 0) continue;

				for(int d=0; d<=i; d++){
					
					int next_b = b | (d<my_p[i]);
					if(b==0 && d>my_p[i]){
						continue;
					}

					dp_[next_b] += dp[b] + d*cnt[b]%MOD;
					dp_[next_b] %= MOD;

					cnt_[next_b] += cnt[b];

				}
			}
			*/
			swap(dp, dp_);
			swap(cnt, cnt_);
		}

		long long ret = (dp[0] + dp[1]) % MOD;
		return ret;
	};

	vector<int> full(len);
	iota(full.begin(), full.end(), 0);

	long long ret = 0;
	ret += tmp[0] * right(p) % MOD;
	ret %= MOD;
	ret += tmp[1] * right(full) % MOD;
	ret %= MOD;
	return ret;
}

int main(){
	long long n,k;
	cin >> n >> k;
	vector<int> p(n);
	for(int i=0; i<n; i++){
		cin >> p[i];
	}

	vector<int> f(n);
	BinaryIndexedTree_1_indexed<int> BIT(n+10);
	long long ans = 0;
	for(int i=n-1; i>=0; i--){
		int cnt = BIT.get_sum(p[i]+1);
		f[n-1-i] = cnt;
		ans += cnt;
		ans %= MOD;
		BIT.add(p[i]+1, 1);
	}

	if(k==0){
		cout << 0 << endl;
		return 0;
	}

	Fuctorial_Number_System start(f);
	Fuctorial_Number_System end_(k-1);
	Fuctorial_Number_System end = start + end_;

	ans = (ans+func(end.f, n)) % MOD;
	ans = (ans-func(start.f, n)+MOD) % MOD;

	cout << ans << endl;


	return 0;
}
0