結果

問題 No.940 ワープ　ε=ε=ε=ε=ε=│;p>д＜│
ユーザー tarattata1tarattata1
提出日時 2019-12-04 19:22:37
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,065 ms / 5,000 ms
コード長 4,708 bytes
コンパイル時間 634 ms
コンパイル使用メモリ 74,840 KB
実行使用メモリ 79,440 KB
最終ジャッジ日時 2024-05-08 05:59:56
合計ジャッジ時間 15,999 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 356 ms
41,844 KB
testcase_01 AC 356 ms
41,936 KB
testcase_02 AC 355 ms
41,856 KB
testcase_03 AC 359 ms
42,020 KB
testcase_04 AC 14 ms
41,800 KB
testcase_05 AC 354 ms
41,920 KB
testcase_06 AC 351 ms
41,884 KB
testcase_07 AC 354 ms
41,936 KB
testcase_08 AC 356 ms
41,984 KB
testcase_09 AC 353 ms
41,976 KB
testcase_10 AC 355 ms
41,900 KB
testcase_11 AC 356 ms
41,916 KB
testcase_12 AC 352 ms
41,788 KB
testcase_13 AC 359 ms
41,960 KB
testcase_14 AC 353 ms
41,908 KB
testcase_15 AC 397 ms
44,316 KB
testcase_16 AC 514 ms
50,052 KB
testcase_17 AC 680 ms
58,712 KB
testcase_18 AC 778 ms
63,892 KB
testcase_19 AC 683 ms
58,540 KB
testcase_20 AC 906 ms
70,252 KB
testcase_21 AC 566 ms
52,772 KB
testcase_22 AC 881 ms
68,852 KB
testcase_23 AC 521 ms
50,568 KB
testcase_24 AC 891 ms
69,680 KB
testcase_25 AC 1,007 ms
75,300 KB
testcase_26 AC 1,065 ms
79,440 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main(int, char**)’:
main.cpp:109:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  109 |     scanf("%d%d%d", &X, &Y, &Z);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

ソースコード

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