結果

問題 No.940 ワープ　ε=ε=ε=ε=ε=│;p>д＜│
ユーザー tarattata1tarattata1
提出日時 2019-12-04 19:22:37
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,106 ms / 5,000 ms
コード長 4,708 bytes
コンパイル時間 645 ms
コンパイル使用メモリ 77,848 KB
実行使用メモリ 79,200 KB
最終ジャッジ日時 2023-08-21 00:16:17
合計ジャッジ時間 17,020 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 356 ms
41,428 KB
testcase_01 AC 357 ms
41,436 KB
testcase_02 AC 356 ms
41,368 KB
testcase_03 AC 360 ms
41,804 KB
testcase_04 AC 15 ms
41,424 KB
testcase_05 AC 358 ms
41,440 KB
testcase_06 AC 357 ms
41,412 KB
testcase_07 AC 357 ms
41,396 KB
testcase_08 AC 356 ms
41,460 KB
testcase_09 AC 356 ms
41,424 KB
testcase_10 AC 356 ms
41,376 KB
testcase_11 AC 356 ms
41,476 KB
testcase_12 AC 360 ms
41,436 KB
testcase_13 AC 358 ms
41,372 KB
testcase_14 AC 356 ms
41,444 KB
testcase_15 AC 404 ms
44,024 KB
testcase_16 AC 521 ms
49,728 KB
testcase_17 AC 692 ms
58,444 KB
testcase_18 AC 795 ms
63,668 KB
testcase_19 AC 691 ms
58,412 KB
testcase_20 AC 921 ms
69,984 KB
testcase_21 AC 576 ms
52,596 KB
testcase_22 AC 892 ms
68,580 KB
testcase_23 AC 531 ms
50,300 KB
testcase_24 AC 910 ms
69,468 KB
testcase_25 AC 1,023 ms
75,108 KB
testcase_26 AC 1,106 ms
79,200 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/**********************************************************
Yukicoder No.940 ワープ　ε=ε=ε=ε=ε=│;p>д＜│
https://yukicoder.me/problems/no/940

＜解法＞
n=X+Y+Z とおく。

nより十分に大きいNをとり、
T=(1+x+x^2+..+x^(N-1))(1+y+y^2+..+y^(N-1))(1+z+z^2+..+z^(N-1))-1
 =(1-x^N)/(1-x) (1-y^N)/(1-y) (1-z^N)/(1-z) -1
とおくと、
F=Σ(m=1..n)T^m の x^X y^Y z^Z の係数を求めればよい。

※理由：x^i y^j z^k というのが、1回の移動でx方向にi、y方向にj、z方向にk 進むことを表していて、
  m回移動したときに(X,Y,Z)に到達する場合の数が T^m の x^X y^Y z^Z の係数と等しいので。

F=Σ(m=1..n)T^m の x^X y^Y z^Z の係数を求めるときには
FをxでX回、yでY回、zでZ回偏微分してx=y=z=0 を入れた値を X!Y!Z! で割ればよい。
この計算を行うときには、Nを十分大きくとっておけば、
T=(1-x^N)/(1-x) (1-y^N)/(1-y) (1-z^N)/(1-z) -1
のかわりに
T=1/(1-x)(1-y)(1-z) -1
として計算してもよいことがわかる。

S=(1-x)^(-1) (1-y)^(-1) (1-z)^(-1) とおくと、
F=Σ(m=1..n)(S-1)^m
 =(S-1)(1-(S-1)^n)/(1-(S-1))
これは、(S-1)^nを二項定理で展開した後、多項式の掛け算、割り算をすれば、Σ(m=1..∞)Am S^m の形に書ける。
（係数Am を m<=n の範囲のみ計算することにすれば O(n)で求まる）

あとは、各 S^m についてx^X y^Y z^Z の係数を求めるには
S^m=(1-x)^(-m) (1-y)^(-m) (1-z)^(-m)
を xでX回、yでY回、zでZ回偏微分してx=y=z=0 を入れればよいが、
これは m(m+1)..(m+X-1) と m(m+1)..(m+Y-1) と m(m+1)..(m+Z-1) の積になる。

**********************************************************/

#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <assert.h>
#pragma warning(disable:4996) 
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
//const long long MOD = 998244353;
using namespace std;

const int max_comb=2500000;
vector<ll> fac(max_comb+1); //n! (mod M)
vector<ll> ifac(max_comb+1); //k!^(-1) (mod M)

ll mpow(ll x, ll n){ //x^n(mod M)
    ll ans = 1;
    while(n != 0){
        if(n&1) ans = ans*x % MOD;
        x = x*x % MOD;
        n = n >> 1;
    }
    return ans;
}

ll minv(ll x){
    return mpow( x, MOD-2 );
}

ll comb(int a, int b){     // C(a,b) = a! * b!^(-1) * (a-b)^(-1)
    if(a == 0 && b == 0)return 1;
    if(a < b || a < 0)return 0;
    ll tmp = ifac[a-b]* ifac[b] % MOD;
    return tmp * fac[a] % MOD;
}

ll perm(int a, int b){     // P(a,b) = a! * (a-b)!^(-1)
    if(b == 0)return 1;
    if(a < b || a < 0)return 0;
    ll tmp = ifac[a-b] % MOD;
    return tmp * fac[a] % MOD;
}

void pre_comb()
{
    fac[0] = 1;
    ifac[0] = 1;
    for(int i = 0; i<max_comb; i++){
        fac[i+1] = fac[i]*(i+1) % MOD; // n!(mod M)
        ifac[i+1] = ifac[i]*minv(i+1) % MOD; // k!^(-1) (mod M)
    }
    return;
}

int main(int argc, char* argv[])
{
    int X,Y,Z;
    scanf("%d%d%d", &X, &Y, &Z);
    int n=X+Y+Z;
    if(n==0) {
        printf("1\n"); return 0;
    }

    pre_comb();

    vector<ll> S(n+1);   // S[m]は、(1-x)^(-m) (1-y)^(-m) (1-z)^(-m) を xでX回、yでY回、zでZ回偏微分してx=y=z=0 を入れた値

    int i;
    for(i=1; i<=n; i++) {
        S[i]=1;
        if(X>0) S[i]=S[i]*perm(i+X-1,X)%MOD;
        if(Y>0) S[i]=S[i]*perm(i+Y-1,Y)%MOD;
        if(Z>0) S[i]=S[i]*perm(i+Z-1,Z)%MOD;
    }

    vector<ll> A(n+1);   // A[i]は、(1-(S-1)^n) の S^i の係数
    for(i=0; i<=n; i++) {
        if(i==0) A[0]=1;
        ll tmp=comb(n,i);
        if((n-i)%2==0) tmp=-tmp;
        A[i]=(A[i]+tmp+MOD)%MOD;
    }

    vector<ll> B(n+1);   // B[i]は、(S-1)(1-(S-1)^n) の S^i の係数 (nより大きい次数は無視）
    for(i=0; i<=n; i++) {
        if(i>0) B[i]=A[i-1];
        B[i]=(B[i]-A[i]+MOD)%MOD;
    }

    vector<ll> C(n+1);   // C[i]は、(S-1)(1-(S-1)^n)/(1-(S-1)) の S^i の係数 (nより大きい次数は無視
    ll curr=0;
    for(i=0; i<=n; i++) {
        curr=(curr+B[i])%MOD;
        C[i]=curr*minv(2)%MOD;
        curr=C[i];
    }

    ll ans=0;
    for(i=1; i<=n; i++) {
        ll tmp=S[i];       // S[i]の値を X!Y!Z! で割る
        if(X>0) tmp=tmp*minv(perm(X,X))%MOD;
        if(Y>0) tmp=tmp*minv(perm(Y,Y))%MOD;
        if(Z>0) tmp=tmp*minv(perm(Z,Z))%MOD;
        ans=(ans+tmp*C[i]%MOD)%MOD;
    }
    printf("%lld\n", ans);

    return 0;
}
0