[bzoj4517] [SDOI2016] 배열 계수

4299 단어

제목의 대의.


a는 n에 대한 배열이다.조건에 맞는 배열이 얼마나 있느냐고 묻는다--마침 m개의 위치가 a[i]=i를 만족시킨다

엇갈리다


dp[i]를 설정하면 i개 요소의 오타 배열 방안 수를 표시합니다.무슨 뜻이죠?바로 i에 대한 배열에 임의의 a[j]=j가 존재하지 않는다.답은 분명히 Cmn∗dp[n-3m] 조합수 빠른 계산으로 곱셈과 곱셈의 역원을 미리 처리할 수 있다.어떻게 dp를 미리 처리합니까?우리는 용척 원리를 사용할 수 있다. 예를 들어 dp[n]는 사실 n개의 조건을 만족시켜야 한다. i개의 조건은 a[i]이다!그럼 합법적인 방안수 = 최소 0개 조건 미만 - 최소 1개 조건 미만 + 최소 2개 조건 미만 - 최소 3개 조건 미만 +... 즉 dp[n]=∑ni=0(-1)i𕓭Cin(n-i)!dp[n]=∑ni=0(−1)i∗n!i!∗(n−i)!∗(n−i)! dp[n]=∑ni=0(−1)i∗n!i! dp[n]=(−1)n+∑n−1i=0(−1)i∗n!i! dp[n]=(−1)n+n∗∑n−1i=0(−1)i∗(n−1)!i! dp[n]=(--1)n+n∗dp[n-3]그래서 우리는 선형적으로 dp수조를 미리 처리할 수 있다.그리고 이 문제는 풀 수 있다.
#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
using namespace std;
typedef long long ll;
const int mo=1000000007,maxn=1000000+10;
int f[maxn],g[maxn],dp[maxn];
int i,j,k,l,t,n,m,ca,ans;
int qsm(int x,int y){
    if (!y) return 1;
    int t=qsm(x,y/2);
    t=(ll)t*t%mo;
    if (y%2) t=(ll)t*x%mo;
    return t;
}
int main(){
    f[0]=1;
    fo(i,1,1000000) f[i]=(ll)f[i-1]*i%mo;
    g[1000000]=qsm(f[1000000],mo-2);
    fd(i,999999,0) g[i]=(ll)g[i+1]*(i+1)%mo;
    dp[0]=1;dp[1]=0;
    fo(i,2,1000000)
        dp[i]=(((ll)dp[i-1]*i%mo+((i%2)?-1:1))%mo+mo)%mo;
    scanf("%d",&ca);
    while (ca--){
        scanf("%d%d",&n,&m);
        ans=(ll)f[n]*g[m]%mo*g[n-m]%mo*dp[n-m]%mo;
        printf("%d
",ans);
    }
}
React.js가 무엇인가요(완전한 초보자용)?
Devise에 대한 단계 설정(Rails)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage