#657746 (C++17) No.1510 Simple Integral

提出ソース

結果

問題	No.1510 Simple Integral
ユーザー	pockyny
提出日時	2021-05-15 00:47:13
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	9,393 bytes
コンパイル時間	4,292 ms
コンパイル使用メモリ	241,804 KB
実行使用メモリ	10,096 KB
最終ジャッジ日時	2024-04-10 05:59:35
合計ジャッジ時間	5,817 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	5 ms 6,812 KB
testcase_01	AC	5 ms 6,940 KB
testcase_02	AC	5 ms 6,940 KB
testcase_03	AC	5 ms 6,944 KB
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	WA	-
testcase_37	WA	-
testcase_38	WA	-
testcase_39	WA	-
testcase_40	WA	-
testcase_41	WA	-
testcase_42	WA	-
testcase_43	WA	-
testcase_44	WA	-
testcase_45	WA	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include<bits/stdc++.h>
using namespace std;
#pragma region atcoder
#include <atcoder/modint>
#include <atcoder/convolution>
using namespace atcoder;
//using mint = modint998244353;
//using mint = modint1000000007;
#pragma endregion
#pragma region debug for var, v, vv
#define debug(var)  do{std::cerr << #var << " : ";view(var);}while(0)
template<typename T> void view(T e){std::cerr << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cerr << e << " "; } std::cerr << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){cerr << endl;int cnt = 0;for(const auto& v : vv){cerr << cnt << "th : "; view(v); cnt++;} cerr << endl;}
#pragma endregion
using ll = long long;
const ll mod = 1000000007;
const int inf = 1001001001;
const ll INF = 1001001001001001001ll; 
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
template<class T, class K>bool chmax(T &a, const K b) { if (a<b) { a=b; return 1; } return 0; }
template<class T, class K>bool chmin(T &a, const K b) { if (b<a) { a=b; return 1; } return 0; }
ll rudiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } //  20 / 3 == 7
ll rddiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // -20 / 3 == -7
ll power(ll a, ll p){ll ret = 1; while(p){if(p & 1){ret = ret * a;} a = a * a; p >>= 1;} return ret;}
ll modpow(ll a, ll p, ll m){ll ret = 1; while(p){if(p & 1){ret = ret * a % m;} a = a * a % m; p >>= 1;} return ret;}
/*---------------------------------------------------------------------------------------------------------------------------------*/
template<class T>
struct FormalPowerSeries : vector<T>{
    using vector<T>::vector;
    using vector<T>::operator=;
    using F = FormalPowerSeries;

    // operations in O(N)
    F operator-()const{
        F res(*this);
        for (auto &e : res) e = -e;
        return res;
    }
    F &operator*=(const T &g) {
        for (auto &e : *this) e *= g;
        return *this;
    }
    F &operator/=(const T &g) {
        assert(g != T(0));
        *this *= g.inv();
        return *this;
    }
    F &operator+=(const F &g) {
        int n = (*this).size(), m = g.size();
        for(int i = 0; i < min(n, m); i++) (*this)[i] += g[i];
        return *this;
    }
    F &operator-=(const F &g) {
        int n = (*this).size(), m = g.size();
        for(int i = 0; i < min(n, m); i++) (*this)[i] -= g[i];
        return *this;
    }
    // f -> f*z^d
    F &operator<<=(const int d) {
        int n = (*this).size();
        (*this).insert((*this).begin(), d, 0);
        (*this).resize(n);
    return *this;
    }
    // f -> f*z^(-d)
    F &operator>>=(const int d) {
        int n = (*this).size();
        (*this).erase((*this).begin(), (*this).begin() + min(n, d));
        (*this).resize(n);
        return *this;
    }
    
    // return 1/f, deg(1/f) = d - 1
    // using atcoder::convolution
    F inv(int d = -1) const {
        int n = (*this).size();
        assert(n != 0 && (*this)[0] != 0);
        if (d == -1) d = n;
        assert(d > 0);
        F res{(*this)[0].inv()};
        while (res.size() < d){
            int m = size(res);
            F f(begin(*this), begin(*this) + min(n, 2*m));
            F r(res);
            f.resize(2*m), internal::butterfly(f);
            r.resize(2*m), internal::butterfly(r);
            for(int i = 0; i < 2*m; i++) f[i] *= r[i];
            internal::butterfly_inv(f);
            f.erase(f.begin(), f.begin() + m);
            f.resize(2*m), internal::butterfly(f);
            for(int i = 0; i < 2*m; i++) f[i] *= r[i];
            internal::butterfly_inv(f);
            T iz = T(2*m).inv(); iz *= -iz;
            for(int i = 0; i < m; i++) f[i] *= iz;
            res.insert(res.end(), f.begin(), f.begin() + m);
        }
        return {res.begin(), res.begin() + d};
    }

// computation for f*g & f/g, use either one of them

    //// fast: FMT-friendly modulus only -> O((N + M)log(N + M))
    /*  F &operator*=(const F &g) {
            int n = (*this).size();
            *this = convolution(*this, g);
            (*this).resize(n);
            return *this;
        }
        F &operator/=(const F &g) {
            int n = (*this).size();
            *this = convolution(*this, g.inv(n));
            (*this).resize(n);
            return *this;
        }
    */

    //// naive -> O(NM)
    /*  F &operator*=(const F &g) {
            int n = (*this).size(), m = g.size();
            for(int i = n - 1; i >= 0; i--) {
                (*this)[i] *= g[0];
                for(int j = 1; j < min(i+1, m); j++) (*this)[i] += (*this)[i-j] * g[j];
            }
            return *this;
        }
        F &operator/=(const F &g) {
            assert(g[0] != T(0));
            T ig0 = g[0].inv();
            int n = (*this).size(), m = g.size();
            for(int i = 0; i < n; i++) {
                for(int j = 1; j < min(i+1, m); j++) (*this)[i] -= (*this)[i-j] * g[j];
                (*this)[i] *= ig0;
            }
            return *this;
        }
    */

    // sparse(the coefficiets in g have K non-0s) O(NK)
    // give the pair of (degree, coefficient) in this function
    // f -> f*g
    F &operator*=(vector<pair<int, T>> g) {
        int n = (*this).size();
        auto [d, c] = g.front();
        if (d == 0) g.erase(g.begin());
        else c = 0;
        for(int i = n - 1; i >= 0; i--){
            (*this)[i] *= c;
            for (auto &[j, b] : g) {
                if (j > i) break;
                (*this)[i] += (*this)[i-j] * b;
            }
        }
        return *this;
    }
    // f -> f/g
    F &operator/=(vector<pair<int, T>> g) {
        int n = (*this).size();
        auto [d, c] = g.front();
        assert(d == 0 && c != T(0));
        T ic = c.inv();
        g.erase(g.begin());
        for(int i = 0; i < n; i++) {
            for (auto &[j, b] : g) {
                if (j > i) break;
                (*this)[i] -= (*this)[i-j] * b;
            }
            (*this)[i] *= ic;
        }
        return *this;
    }

    // f -> f*(1 + c*z^d) in O(N)
    void multiply(const int d, const T c) { 
        int n = (*this).size();
        if (c == T(1)) for(int i = n-d-1; i >= 0; i--) (*this)[i+d] += (*this)[i];
        else if (c == T(-1)) for(int i = n-d-1; i >= 0; i--) (*this)[i+d] -= (*this)[i];
        else for(int i = n-d-1; i >= 0; i--) (*this)[i+d] += (*this)[i] * c;
    }

    // f -> f/(1 + c*z^d) in O(N)
    void divide(const int d, const T c) {
        int n = (*this).size();
        if (c == T(1)) for(int i = 0; i < n-d; i++) (*this)[i+d] -= (*this)[i];
        else if (c == T(-1)) for(int i = 0; i < n-d; i++) (*this)[i+d] += (*this)[i];
        else for(int i = 0; i < n-d; i++) (*this)[i+d] -= (*this)[i] * c;
    }

    // return f(a)
    T eval(const T &a) const {
        T x(1), res(0);
        for (auto e : *this) res += e * x, x *= a;
        return res;
    }

    F operator*(const T &g)const{return F(*this) *= g;}
    F operator/(const T &g)const{return F(*this) /= g;}
    F operator+(const F &g)const{return F(*this) += g;}
    F operator-(const F &g)const{return F(*this) -= g;}
    F operator<<(const int d)const{return F(*this) <<= d;}
    F operator>>(const int d)const{return F(*this) >>= d;}
    F operator*(const F &g)const{return F(*this) *= g;}
    F operator/(const F &g)const{return F(*this) /= g;}
    F operator*(vector<pair<int, T>> g)const{ return F(*this) *= g;}
    F operator/(vector<pair<int, T>> g)const{ return F(*this) /= g;}
};  
using mint = modint998244353;
using fps = FormalPowerSeries<mint>;
using sfps = vector<pair<int, mint>>;

mint a[110];
typedef long long ll;
ll MOD = 998244343;
mint pw(mint a,ll x){
    mint ret = 1;
    while(x){
        if(x&1) (ret *= a);
        (a *= a); x /= 2;
    }
    return ret;
}

vector<ll> d;
mint A[110];
ll cnt[1000010] = {};
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    //cout << fixed << setprecision(20);
    int i,j,n;
    mint pr = -1,u = -1; cin >> n;
    MOD--;
    for(i=1;i*i<MOD;i++){
        if(MOD%i==0){
            if(i!=1 && i!=MOD) d.push_back(i);
            if(i!=1 && i!=MOD) d.push_back(MOD/i);
        }
    }
    MOD++;
    for(i=2;i<MOD;i++){
        bool f = true;
        for(int x:d){
            if(pw(i,x)==1) f = false;
        }
        if(f){
            pr = i;
            break;
        }
    }
    u = pw(pr,(MOD - 1)/4);
    if(pr==-1 || u==-1) exit(1);
    for(i=0;i<n;i++){
        int x; cin >> x; A[i] = x;
        cnt[x]++;
    }
    mint ans = 0;
    for(i=1;i<=1000000;i++){
        if(!cnt[i]) continue;
        fps f(100);
        f[0] = 1;
        int num = 0;
        for(j=0;j<n;j++){
            if(i==A[j]){
                num++;
              	continue;
            }
            fps g(2);
            g[2] = 1; g[1] = -2*u*i; g[0] = A[j]*A[j] - i*i;
            f = convolution(f,g);
        }
      /*cout << i << " " << num << endl;
      for(auto x:f) cout << x.val() << " ";*/
        f = f.inv();
        ans += f[num - 1]/pw((mint)2*u*i,num);
    }
    ans *= (mint)2*u;
    cout << ans.val() << endl;
    /*for(int i = 0; i < n; i++){
        int x; cin >> x;
        f[i] = x;
    }
    f = f.inv();
    for(int i = 0; i < n; i++) cout << f[i].val() << " ";
    cout << endl;*/
}       
/*
   * review your code when you get WA (typo? index?)
   * int overflow, array bounds
   * special cases (n=1?)
*/

yukicoder

結果

テストケース

ソースコード