NC213882. CCA的树
描述
输入描述
一行，两个整数 n , m
输出描述
一行，一个整数表示染色方案数的期望对 1023694381 取模后的值 。
示例1
输入:
4 2
输出:
8
C++(clang++11) 解法, 执行用时: 254ms, 内存消耗: 156792K, 提交时间: 2020-12-21 00:03:38
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
typedef long long ll;
const int N=1e7+4;
const ll M=1023694381ll;
using namespace std;
ll n,m,s[N],inv[N];
ll pm(ll x,ll b){x%=M;ll res=1;while(b){if(b&1)res=res*x%M;b>>=1;x=x*x%M;}return res;}
ll C(ll n,ll m){return s[n]*inv[m]%M*inv[n-m]%M;}
void f1(){
scanf("%lld%lld",&n,&m);
s[0]=1;
int nn=max(n,m);
for(int i=1;i<=nn;i++)s[i]=s[i-1]*i%M;
inv[nn]=pm(s[nn],M-2);inv[0]=1;
for(int i=nn-1;i>=1;i--)inv[i]=inv[i+1]*(i+1)%M;
ll ans=pm(m,n);
for(ll i=0;i<=n-1;i++){
if(i+1<=m)ans=(ans-C(m,i+1)*C(n-1,i)%M*s[i+1]%M+M)%M;
}
printf("%lld",ans);
}
int main(){
f1();
return 0;
}