結果

問題 No.940 ワープ　ε=ε=ε=ε=ε=│;p>д＜│
コンテスト
ユーザー tarattata1
提出日時 2019-12-04 13:32:54
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 1,006 ms / 5,000 ms
コード長 4,149 bytes
コンパイル時間 642 ms
コンパイル使用メモリ 74,468 KB
実行使用メモリ 79,392 KB
最終ジャッジ日時 2024-11-30 08:03:59
合計ジャッジ時間 14,809 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 22
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main(int, char**)’:
main.cpp:97:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   97 |     scanf("%d%d%d", &X, &Y, &Z);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

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

＜解法＞
n=X+Y+Z
T=(1+x+x^2+..)(1+y+y^2+..)(1+z+z^2+..)-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 の係数と等しいので。

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 の形に書ける。
（実際は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];
        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