[BZOJ4487][JSOI2015] 염색 문제(용척)
세 가지 조건: 유색 행수 n, 유색 열수 m, 색수 p, 3차원 용척 원리는 여전히 성립된다.
$\sum{i=0}^{n}\sum_{j=0}^{m}\sum_{k=0}^{p}(-1)^{n+m+p-i-j-k}\times C_n^i\times C_m^j\times C_p^k\times (k+1)^{ij}$
복잡도 $O (n^3)$
2항식 정리에 따라 최적화할 수 있다.
https://blog.csdn.net/werkeytom_ftd/article/details/52527740
복잡도 $O(n^2\log)$
1 #include
2 #include
3 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
4 using namespace std;
5
6 const int N=410,mod=1e9+7;
7 int n,m,p,ans,fac[N],inv[N];
8
9 int ksm(int a,int b){
10 int res=1;
11 for (; b; a=1ll*a*a%mod,b>>=1)
12 if (b & 1) res=1ll*res*a%mod;
13 return res;
14 }
15
16 int C(int n,int m){ return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod; }
17
18 int main(){
19 freopen("bzoj4487.in","r",stdin);
20 freopen("bzoj4487.out","w",stdout);
21 scanf("%d%d%d",&n,&m,&p);
22 fac[0]=1; rep(i,1,400) fac[i]=1ll*fac[i-1]*i%mod;
23 inv[400]=ksm(fac[400],mod-2);
24 for (int i=399; ~i; i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;
25 rep(i,0,n) rep(k,0,p){
26 int t=1ll*C(n,i)*C(p,k)%mod*ksm((1-ksm(k+1,i)+mod)%mod,m)%mod;
27 if ((n+m+p-i-k)&1) ans=(ans-t+mod)%mod; else ans=(ans+t)%mod;
28 }
29 printf("%d
",ans);
30 return 0;
31 }
전재 대상:https://www.cnblogs.com/HocRiser/p/10054896.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.