A - Character Encoding

?HDU - 6397?

思路 ：

隔板法就是在n個元素間的（n-1）個空中插入k-1個板，可以把n個元素分成k組的方法

普通隔板法
?求方程 x+y+z=10的正整數解的個數。

添元素隔板法
?求方程 x+y+z=10的非負整數解的個數。 那么 增加 3 即轉化為 了普通隔板法? ?

但是這個題呢 還有 < N 的限制 ，那么就需要去除掉? ，分出的塊中 有 > = n 的情況 。

就會 有 一塊 出現 > =n ,兩塊 > =n 等等。。 具體 需要根據總數來確定 ，要去除這些情況貢獻的解?

發現? 如果 有某一塊 > = n 那么就轉化為了 先把n個? 放到 某一塊上 ，剩下的 總數 - n? 再 進行 分為 m塊的 分配，

計算式即為 。 某一塊?????* ?? （剩下的 分到 m塊上） 但是這樣會多減去一些，因為 這些情況中包含了

有 兩塊? > = n 三塊 > =n 等等 。所以 需要 加回來 兩塊的情況，

#include<bits/stdc++.h> using namespace std; #define maxn 234567 #define ll long long #define mod 998244353 ll n,m,k,inv[maxn+10],A[maxn+10],ans,t; ll qpow(ll a,ll b) {ll re=1;while(b){if(b%2)re=(re*a)%mod;a=(a*a)%mod;b>>=1;}return re; } void init() {A[0]=inv[0]=1;for(int i=1; i<=maxn; i++){A[i]=(A[i-1]*i)%mod;inv[i]=qpow(A[i],mod-2)%mod;} } ll C(ll a,ll b) {if(b<a)return 0;return (A[b]*inv[a]%mod*inv[b-a])%mod; } int main() {init();scanf("%lld",&t);while(t--){ans=0;scanf("%lld%lld%lld",&n,&m,&k);if(k==0)printf("1\n");else if(k>m*(n-1))printf("0\n");else if(k<n) printf("%lld\n",C(m-1,m+k-1));else{ll x=-1;ans=C(m-1,m+k-1);for(int i=1; i<=m; i++){ans=(ans+C(i,m)*x%mod*C(m-1,k+m-1-i*n)%mod+mod)%mod;x*=-1;}printf("%lld\n",ans);}}return 0; }

　　

轉載于:https://www.cnblogs.com/SDUTNING/p/10261605.html

總結

以上是生活随笔為你收集整理的A - Character Encoding HDU - 6397 - 方程整数解-容斥原理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。