結果

問題 No.1263 ご注文は数学ですか？
ユーザー msm1993
提出日時 2020-10-23 15:40:10
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 24 ms / 2,000 ms
コード長 7,019 bytes
コンパイル時間 1,670 ms
コンパイル使用メモリ 132,904 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-21 10:08:07
合計ジャッジ時間 1,931 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#include <list>
#define popcount __builtin_popcount
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
template<int MOD>
struct ModInt{
    int x;
    ModInt(): x(0){}
    ModInt(ll y): x(y>=0 ? y%MOD : (MOD-(-y)%MOD)%MOD){}
    ModInt &operator+=(const ModInt &p){
        if((x+=p.x)>=MOD) x-=MOD;
        return *this;
    }
    ModInt &operator-=(const ModInt &p){
        if((x+=MOD-p.x)>=MOD) x-=MOD;
        return *this;
    }
    ModInt &operator*=(const ModInt &p){
        x=(int)(1ll*x*p.x%MOD);
        return *this;
    }
    ModInt &operator/=(const ModInt &p){
        *this*=p.inv();
        return *this;
    }
    ModInt operator-() const{ return ModInt(-x);}
    ModInt operator+(const ModInt &p) const{ return ModInt(*this)+=p;}
    ModInt operator-(const ModInt &p) const{ return ModInt(*this)-=p;}
    ModInt operator*(const ModInt &p) const{ return ModInt(*this)*=p;}
    ModInt operator/(const ModInt &p) const{ return ModInt(*this)/=p;}
    bool operator==(const ModInt &p) const{ return x==p.x;}
    bool operator!=(const ModInt &p) const{ return x!=p.x;}
    ModInt pow(ll n) const{
        ModInt ret(1), p(x);
        while(n){
            if(n&1) ret*=p;
            p*=p;
            n>>=1;
        }
        return ret;
    }
    ModInt inv() const{
        return pow(MOD-2);
    }
};
const int MOD=1e9+7;
using mint=ModInt<MOD>;
template<typename T>
struct Matrix{
    vector<vector<T>> a;
    Matrix(){}
    Matrix(size_t n, size_t m):a(n, vector<T>(m, 0)){}
    Matrix(size_t n):Matrix(n, n){}
    Matrix(vector<vector<T>> a):a(a){}
    size_t height() const{
        return a.size();
    }
    size_t width() const{
        return a[0].size();
    }
    inline const vector<T> &operator[](size_t k) const{
        return a[k];
    }
    inline vector<T> &operator[](size_t k){
        return a[k];
    }
    static Matrix I(size_t n){
        Matrix mat(n);
        for(int i=0; i<n; i++) mat[i][i]=1;
        return mat;
    }
    Matrix &operator+=(const Matrix &b){
        size_t n=height(), m=width();
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                (*this)[i][j]+=b[i][j];
            }
        }
        return (*this);
    }
    Matrix &operator-=(const Matrix &b){
        size_t n=height(), m=width();
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                (*this)[i][j]-=b[i][j];
            }
        }
        return (*this);
    }
    Matrix &operator*=(const Matrix &b){
        size_t n=height(), m=width(), l=b.width();
        vector<vector<T>> c(n, vector<T>(l, 0));
        for(int i=0; i<n; i++){
            for(int j=0; j<l; j++){
                for(int k=0; k<m; k++){
                    c[i][j]+=(*this)[i][k]*b[k][j];
                }
            }
        }
        a.swap(c);
        return (*this);
    }
    Matrix operator+(const Matrix &b) const{
        return (Matrix(*this)+=b);
    }
    Matrix operator-(const Matrix &b) const{
        return (Matrix(*this)-=b);
    }
    Matrix operator*(const Matrix &b) const{
        return (Matrix(*this)*=b);
    }
    Matrix pow(ll k) const{
        Matrix ap(a), ret=I(height());
        while(k){
            if(k&1) ret*=ap;
            ap*=ap;
            k>>=1;
        }
        return ret;
    }
    static pair<Matrix, Matrix> Gauss_Jordan(const Matrix &a, const Matrix &b){
        size_t n=a.height(), m=a.width(), l=b.width();
        Matrix c(n, m+l);
        for(int i=0; i<n; i++) for(int j=0; j<m; j++) c[i][j]=a[i][j];
        for(int i=0; i<n; i++) for(int j=0; j<l; j++) c[i][j+m]=b[i][j];
        int d=0;
        for(int i=0; i<m; i++){
            int p=-1; 
            for(int j=d; j<n; j++){
                if(c[j][i]!=0){
                    p=j; break;
                }
            }
            if(p==-1) continue;
            swap(c[p], c[d]);
            T invc=T(1)/c[d][i];
            for(int j=i; j<m+l; j++) c[d][j]*=invc;
            for(int j=0; j<n; j++){
                if(j==d) continue;
                T c0=c[j][i];
                for(int k=i; k<m+l; k++){
                    c[j][k]-=c0*c[d][k];
                }
            }
            d++;
        }
        Matrix reta(n, m), retb(n, l);
        for(int i=0; i<n; i++) for(int j=0; j<m; j++) reta[i][j]=c[i][j];
        for(int i=0; i<n; i++) for(int j=0; j<l; j++) retb[i][j]=c[i][j+m];
        return make_pair(reta, retb);
    }
    static pair<vector<T>, vector<vector<T>>> linear_equations(const Matrix &a, const vector<T> &b){
        int n=a.height(), m=a.width();
        Matrix B(n, 1);
        for(int i=0; i<n; i++) B[i][0]=b[i];
        auto p=Gauss_Jordan(a, B);
        vector<int> myon(n,-1);
        vector<int> nuo(m, -1);
        for(int i=0; i<n; i++){
            bool allzero=1;
            for(int j=0; j<m; j++){
                if(p.first[i][j]!=0){
                    allzero=0;
                    myon[i]=j;
                    nuo[j]=i;
                    break;
                }
            }
            if(allzero && p.second[i][0]!=0){
                vector<T> retc;
                vector<vector<T>> retd;
                return make_pair(retc, retd);
            }
        }
        vector<T> c(m);
        vector<vector<T>> d;
        for(int i=0; i<m; i++){
            if(nuo[i]==-1){
                vector<T> v(m);
                v[i]=1;
                for(int j=0; j<n; j++){
                    if(myon[j]!=-1) v[myon[j]]=-p.first[j][i];
                }
                d.push_back(v);
            }else{
                c[i]=p.second[nuo[i]][0];
            }
        }
        return make_pair(c, d);
    }
    Matrix inv() const{
        int n=height();
        Matrix b=I(n);
        auto p=Gauss_Jordan(*this, b);
        if(p.first[n-1][n-1]==0){
            Matrix ret(0);
            return ret;
        }
        return p.second;
    }
    int rank() const{
        int n=height(), m=width();
        Matrix b(n, 0);
        auto p=Gauss_Jordan(*this, b);
        for(int i=0; i<n; i++){
            bool allzero=1;
            for(int j=0; j<m; j++){
                if(p.first[i][j]!=0){
                    allzero=0;
                    break;
                }
            }
            if(allzero) return i;
        }
        return n;
    }
    T det() const{
        size_t n=height();
        Matrix A(a);
        T ret(1);
        for(int i=0; i<n; i++){
            int p=-1; 
            for(int j=i; j<n; j++){
                if(A[j][i]!=0){
                    p=j; break;
                }
            }
            if(p==-1){
                return 0;
            }
            if(p!=i) ret*=(-1);
            swap(A[p], A[i]);
            ret*=A[i][i];
            T inva=T(1)/A[i][i];
            for(int j=i+1; j<n; j++){
                T a0=A[j][i];
                for(int k=i; k<n; k++){
                    A[j][k]-=inva*a0*A[i][k];
                }
            }
        }
        return ret;
    }
};
using mat=Matrix<mint>;
vector<vector<int>> w;
void gen_bunkatu(vector<int> v, int t, int s){
    if(t==s){
        vector<int> vs=v;
        reverse(vs.begin(), vs.end());
        w.push_back(vs);
        return;
    }
    int m=s;
    if(t) m=v.back();
    for(int i=1; i<=min(m, s-t); i++){
        v.push_back(i);
        gen_bunkatu(v, t+i, s);
        v.pop_back();
    }
}
int main()
{
    int x; cin>>x;
    vector<int> v0;
    gen_bunkatu(v0, 0, x);
    int n=w.size();
    mat a(n);
    vector<mint> b(n);
    for(int i=0; i<n; i++){
        vector<int> v;
        int t=0;
        for(int j=0; j<w[i].size(); j++){
            for(int k=0; k<w[i][j]; k++) v.push_back(t);
            t++;
        }
        if(w[i].size()==x) b[i]=mint(1);
        for(int j=0; j<n; j++){
            bool ok=0;
            do{
                int s=0;
                bool dame=0;
                for(auto p:w[j]){
                    for(int k=s; k<s+p-1; k++){
                        if(v[k]!=v[k+1]){
                            dame=1;
                        }
                    }
                    s+=p;
                    if(dame) break;
                }
                if(!dame){
                    a[i][j]+=mint(1);
                }
            }while(next_permutation(v.begin(), v.end()));
            //cout<<a[i][j].x<<" ";
        }
        //for(auto x:v) cout<<x<<" ";
        //cout<<endl;
    }
    vector<mint> c=mat::linear_equations(a, b).first;
    mint f(1);
    for(int i=1; i<=x; i++) f*=mint(i);
    mint ans(1);
    for(auto z:c) ans*=z*f;
    cout<<ans.x<<endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0