結果

問題 No.696 square1001 and Permutation 5
コンテスト
ユーザー どらら
提出日時 2018-06-09 00:33:24
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,057 bytes
コンパイル時間 2,051 ms
コンパイル使用メモリ 182,640 KB
実行使用メモリ 217,052 KB
最終ジャッジ日時 2024-06-30 12:06:17
合計ジャッジ時間 24,601 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

class BIT{
  static const int MAX_N = 1 << 21;
  int n;
  vector<int> bit;
public:
  BIT(int n_):bit(MAX_N+1){
    n = n_;
    for(int i=0; i<n+1; i++) bit[i] = 0;
  }
  int sum(int i){
    int s = 0;
    while(i>0){
      s+=bit[i];
      i-=i&(-i);
    }
    return s;
  }
  void add(int i, int x){
    while(i<=n){
      bit[i]+=x;
      i+=i&(-i);
    }
  }
};


const long double PI = 4.0 * atan(1);
typedef std::vector< std::complex<long double> > VComp;

void fft(VComp& a, long double theta){
  int n = a.size();
  for(int m=n; m>=2; m>>=1){
    for(int i=0; i<(m>>1); i++){
      std::complex<long double> w = exp(i*theta*std::complex<long double>(0,1));
      for(int j=i; j<n; j+=m){
        int k=j+(m>>1);
        std::complex<long double> x = a[j]-a[k];
        a[j] += a[k];
        a[k] = w*x;
      }
    }
    theta *= 2;
  }

  int i=0;
  for(int j=1; j<n-1; j++){
    for(int k=n>>1; k>(i^=k); k>>=1);
    if(j<i) swap(a[i], a[j]);
  }
  
  if(theta<0){
    for(int i=0; i<a.size(); i++){
      a[i] /= n;
    }
  }
}

VComp str2vec(const std::string& str, int n){
  VComp ret(n, std::complex<long double>(0,0));
  for(int i=str.length()-1,j=0; i>=0; i--,j++){
    ret[j] = str[i] - '0';
  }
  return ret;
}

VComp VComp_mult(const VComp& a, const VComp& b){
  VComp ret(a.size(), std::complex<long double>(0,0));
  for(int i=0; i<a.size(); i++){
    ret[i] = a[i] * b[i];
  }
  return ret;
}


void print(const VComp& v){
  for(int i=0; i<v.size(); i++){
    std::cout << i << " : " << real(v[i]) << " " << imag(v[i]) << std::endl;
  }
}

std::string fft_multi(const std::string& str1, const std::string& str2){
  int n = 1;
  while(str1.size()+str2.size() >= n) n <<= 1;

  VComp ret1 = str2vec(str1, n);
  VComp ret2 = str2vec(str2, n);
  fft(ret1, 2 * PI / n);
  fft(ret2, 2 * PI / n);
  VComp ret = VComp_mult(ret1, ret2);

  fft(ret, -2 * PI / n);
  //print(ret);

  std::string ans = "";
  int carry = 0;
  int nonzero_idx = 0;
  for(int i=0; i<ret.size(); i++){
    if(real(ret[i])<0) ret[i] *= 0;
    if(i == 0){
      ans += (char)('0' + (int)(real(ret[i])+0.5)%10);
    }else{
      int tmp = carry + (int)(real(ret[i-1])+0.5)/10 + (int)(real(ret[i])+0.5)%10;
      carry = carry/10 + tmp/10;
      tmp %= 10;
      ans += (char)('0' + tmp);
      if(tmp != 0) nonzero_idx = i;
    }
  }
  if(carry > 0){
    ans += (char)('0' + carry);
    nonzero_idx = ret.size();
  }

  std::string noleadingzero = ans.substr(0,nonzero_idx+1);
  std::reverse(noleadingzero.begin(), noleadingzero.end());

  return noleadingzero;
}


string ull2str(ull num){
  if(num == 0) return "0";
  string ret = "";
  while(num>0){
    ret += '0' + (num%10);
    num /= 10;
  }
  reverse(ALLOF(ret));
  return ret;
}

string str_add(const string& p, const string& q){
  int l = max(p.size(), q.size());
  deque<int> ret;
  int pi=p.size()-1, qi=q.size()-1;
  int c = 0;
  while(pi>=0 || qi>=0){
    int pp = 0, qq = 0;
    if(pi>=0) pp = p[pi]-'0';
    if(qi>=0) qq = q[qi]-'0';

    ret.push_back((c=(pp)+(qq)+c/10)%10);
    pi--;
    qi--;
  }
  while(c/10 > 0){
    ret.push_back((c/10)%10);
    c /= 10;
  }
  string rets = "";
  for(int i=ret.size()-1; i>=0; i--){
    rets += '0' + ret[i];
  }
  return rets;
}

int main(){
  int N;
  cin >> N;
  vector<int> v;
  rep(i,N){
    int p;
    cin >> p;
    v.push_back(p);
  }
  
  BIT bit(1<<20);
  vector<string> v_num(N);
  vector<string> v_p(N);
  string p = "1";
  for(int i=N-1; i>=0; i--){
    ull num = bit.sum(v[i]);
    v_num[i] = ull2str(num);
    v_p[i] = p;
    p = fft_multi(p, ull2str(N-i));
    bit.add(v[i], 1);
  }
  
  string ret = "1";
  rep(j,N){
    string tmp_nump = fft_multi(v_num[j], v_p[j]);
    ret = str_add(ret, tmp_nump);
  }

  cout << ret << endl;
  
  return 0;
}
0