結果
| 問題 | No.271 next_permutation (2) |
| ユーザー |
 koyumeishi
|
| 提出日時 | 2015-08-25 14:51:11 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 4,999 bytes |
| コンパイル時間 | 899 ms |
| コンパイル使用メモリ | 80,636 KB |
| 最終ジャッジ日時 | 2024-11-14 19:09:44 |
| 合計ジャッジ時間 | 1,886 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、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);
| ^~~~
ソースコード
#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-indexedvoid add(int i, const T x){while(i <= N){tree[i] += x;i += i & -i;}}//update node i to zerovoid 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 1000000007long 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 -> 1dp_[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 -> 0dp_[0] += dp[0] * 1 + my_p[i] * cnt[0] % MOD;dp_[0] %= MOD;cnt_[0] += cnt[0] * 1;cnt_[0] %= MOD;}{ // 1 -> 1dp_[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;}