배열 조합 --- 칸막이 법

1. 정의
  칸막이 법 은 n 개의 요소 사이 에 (b - 1) 개의 판 을 삽입 하 는 것 이다. 즉, n 개의 요 소 를 b 조로 나 누 는 방법 이다.C(n-1,b-1)
 2. 조건
  칸막이 법 은 반드시 세 가지 조건 을 만족 시 켜 야 한다.
 (1) 이 n 개의 요 소 는 반드시 같 아야 한다. (2) 나 누 어 진 각 조 는 적어도 하나의 요 소 를 나 누 어야 한다. (3) 나 누 어 진 조 는 서로 차이 가 있다.
 3. 예시  
(1) 예 를 들 어 한 학교 에서 한 팀 을 구성 하려 면 16 명 이 필요 하 다. 이 학 교 는 모두 10 개 반 이 고 각 반 에 적어도 한 명의 정원 을 배정 하 며 모두 몇 가지 상황 이 있다.C（16-1,10-1）。
   n 개의 동일 한 물품 (또는 정원) 을 m 개인 (또는 위치) 에 게 나 누 어 주 고 몇 명의 개인 (또는 위치) 을 비 워 두 는 문 제 를 볼 수 있 습 니 다. 이 n 개의 물품 을 m 조로 나 누 어 여러 조 를 비 워 두 는 문제 로 볼 수 있 습 니 다. n 개의 물품 을 m 조로 나 누 려 면 m - 1 개의 칸막이 가 필요 합 니 다. 이 n 개의 물품 과 m - 1 개의 칸 막 이 를 한 줄 로 나 누 어 n + m - 1 의 위 치 를 차지 합 니 다. 이 n + m - 1 개의 위치 에서 m - 1 개의 위 치 를 선택 하여 칸 막 이 를 놓 습 니 다.칸막이 에 차이 가 없 기 때문에 칸막이 사이 의 무질서 함 은 조합 문제 이다. 그러므로 칸막이 에는 Cn + m - 1m - 1 가지 다른 방법 이 있 고 물품 을 다른 위치 에 두 면 물품 이 같 고 차이 가 없 기 때문에 물품 간 에 순서 가 없고 조합 문제 이다. 단지 1 가지 방법 만 있 을 뿐 단계별 계수 원리 에 따라 모두 Cn + m - 1 m - 1 이 있다.×1 = Cn + m - 1m - 1 종 배열 법
(2) 방정식 x1 + x2 +... + xk = n 의 비 마이너스 정수 해 또는 정수 해 를 구한다.
   해: 정수 해: 똑 같은 공 10 개 로 바 뀌 어 4 개의 서로 다른 상 자 를 넣 고 한 상자 에 적어도 하나, C (10 - 1, 4 - 1) = 84 가지 가 있다.
       마이너스 정수 분해: 같은 공 10 개 로 전환 하여 4 개의 서로 다른 상 자 를 넣 으 면 빈 상자 가 있 고 C (10 + 4 - 1, 4 - 1) 종이 있다.
(3) X 개의 똑 같은 공 을 Y 개의 서로 다른 상자 에 넣 고 상자 마다 N 개의 공 을 최소 0 개 이상 넣 으 라 고 요구 하 는데 모두 몇 가지 다른 방법 이 있 습 니까?
    먼저 m 개의 공 을 Y 개의 상자 에 넣 고 각 상자 에 적어도 한 개의 공 을 넣 는 방법 은 칸막이 법 으로 얻 을 수 있다. 즉, m - 1 개의 위치 에 Y - 1 개의 댐퍼 를 넣 고 m 개의 공 을 Y 로 나 누 는 것 과 같다. 그러면 각 공 은 적어도 1 이다.
    그리고 X 개의 공 을 Y 개의 상자 에 넣 으 면 각 상자 에 최소 0 개의 공 을 넣 는 방법 은 X + Y 개의 공 을 Y 개의 상자 에 넣 는 것 과 같 습 니 다. 각 상자 에 적어도 하나의 공 을 넣 는 방법 은 X + Y 개의 공 을 Y 개의 상자 에 나 누 어 넣 은 다음 에 각 상자 에서 1 구 를 꺼 내 는 것 과 같 습 니 다.
    그리고 지정 한 t 개의 상자 (예 를 들 어 1, 2, 3, · ·, t 번 상자) 의 공 수 는 적어도 N + 1 개의 공 을 넣 는 방법 과 같다. (X - t * (N + 1) 개의 공 을 Y 개의 상자 에 넣 고 각 상자 에 최소 0 개의 공 을 넣 는 방법, 즉 (X - t * (N + 1) 개의 공 을 Y 개의 상자 에 넣 은 다음 에 지 정 된 t 개의 상자 에 각각 N + 1 개의 공 을 넣 는 것 과 같다.
    용 척 원리 에 따 르 면 각 상자 에서 N 공 까지 의 방 법 은 총 방 법 - 한 상 자 를 지정 하 는 모든 공의 수가 N 보다 큰 방법 + 두 상 자 를 지정 하 는 모든 공의 수가 N 보다 큰 방법 - 세 상 자 를 지정 하 는 모든 공의 수가 N 보다 큰 방법 + · · · · · · ·
즉시
그 속
제목 링크

#include 
using namespace std;
typedef long long ll;
const ll mod=998244353;

ll n,m,k;

const ll M=2*1e5+5;
ll fact[M],ifact[M];//fact[i] i   ，ifact[i]        ，        

ll pow_mod(ll n,ll k,ll mod) //    n^k m   
{
    ll res=1;
    n=n%mod;
    while(k>0)
    {
        if(k&1)
            res=res*n%mod;
        n=n*n%mod;
        k>>=1;
    }
    return res;
}
void init()//   
{
    fact[0]=ifact[0]=1;
    for(int i=1;i