제출 #1344974

#제출 시각아이디문제언어결과실행 시간메모리
1344974vjudge1NoM (RMI21_nom)C++17
100 / 100
33 ms2068 KiB
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#ifdef _WIN32
#define getchar _getchar_nolock
#define putchar _putchar_nolock
#else
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef __int128 i128;
namespace io {
    using namespace std;
    template <typename T> void debug (T x) {
        cerr<<x<<'\n';
    }
    template <typename T> void debuglen (T x) {
        cerr<<x<<' ';
    }
    template <typename T,typename...Args> void debug (T x,Args...args) {
        cerr<<x<<' ';
        debug(args...);
    }
    template <typename T> void debug (T*lt,T*rt) {
        ll len=rt-lt;
        for (ll i=0;i<len;i++) {
            debuglen(*(lt+i));
        }
        cerr<<'\n';
    }
    inline ll read () {
        char x=getchar();
        ll ans=0,f=1;
        while (x<'0'||x>'9') {
            if (x=='-') {
                f=-1;
            }
            x=getchar();
        }
        while (x>='0'&&x<='9') {
            ans=(ans<<1)+(ans<<3);
            ans+=(x^'0');
            x=getchar();
        }
        return ans*f;
    }
    void print (ll x) {
        if (x<0) {
            x=-x;
            putchar('-');
        }
        if (x>=10) {
            print(x/10);
        }
        putchar(x%10+'0');
    }
}
using namespace io;
const ll N=1e5+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
ll n,m,sum[N],inv[N],f[N],kl[N],cnt[N];
inline void init () {
    sum[0]=sum[1]=inv[0]=inv[1]=1;
    for (ll i=2;i<=N-5;i++) {
        inv[i]=inv[mod%i]*(mod-mod/i)%mod;
    }
    for (ll i=2;i<=N-5;i++) {
        sum[i]=sum[i-1]*i%mod;
        inv[i]=inv[i-1]*inv[i]%mod;
    }
}
inline ll calc (ll x,ll y) {
    if (y<0||x<y) {
        return 0;
    }
    return sum[x]*inv[y]%mod*inv[x-y]%mod;
}
inline void solve () {
    init();
    n=read(),m=read();
    for (ll i=1;i<=(n<<1);i++) {
        cnt[i%m]++;
    }
    ll pos=0;
    f[0]=1;
    for (ll i=0;i<m;i++) {
        for (ll j=0;j<=(pos>>1);j++) {
            for (ll k=0;k<=(cnt[i]>>1);k++) {
                kl[j+k]=(kl[j+k]+calc(j+k,k)*f[j]%mod*sum[cnt[i]]%mod*inv[cnt[i]-(k<<1)]%mod)%mod;
            }
        }
        pos+=cnt[i];
        for (ll j=0;j<=(pos<<1);j++) {
            f[j]=kl[j];
            kl[j]=0;
        }
    }
    ll ans=0;
    for (ll i=0;i<=(pos>>1);i++) {
        ll num=calc(n,i)*f[i]%mod*sum[(n-i)<<1]%mod;
        ans=(ans+(i&1?mod-num:num))%mod;
    }
    print(ans);
}
int main () {
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ll T=1;
    // T=read();
    while (T--) {
        solve();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...