Character Encoding(hdu 6397 组合数容斥)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6397
题意：M个位置，每个位置放不超过N的数，求是这些位置加起来的和为K的方案数?
如果没有“每个位置放不超过N的数”这样的限制，那就是很经典的隔板法了
普通的隔板法就是每个位置的数都要大于0，就是 CM−1K $C_K^{M-1}$
而可以为0的隔板法就是考虑极端的情况，有 M−1 $M-1$ 个位置都是 0 $0$ ，这个时候在这 M−1 $M-1$ 个位置都放一个物品，相当于总的物品有 K+M−1 $K+M-1$ 个，于是就变成了 CM−1K+M−1 $C_{K+M-1}^{M-1}$

对容斥理解不深入T_T，当时也想到这样：0个位置超了-1个位置超了+2个位置超了-3个位置超了….
但是我还想的是假如一个位置只超了一个物品，或者超了两个物品，或者超了三个物品…怎么办？这样感觉情况好多啊，但是其实不用考虑这些，我也不理解为什么不考虑这些，只能感觉这些情况会被容斥干掉。。。

这道题和51nod上的这道1269 Devu and Flowers 很类似，这个就是每个位置限制的数不一样

然后这道题我一直wa，以为我是组合数模板有问题，后来找到原因是因为 Cmn $C_n^m$中的 m $m$比 n $n$大了，要返回 0 $0$

#include"bits/stdc++.h"
#define C(n,m) ((long long)fac[(n)]*invf[(m)]%MOD*invf[(n)-(m)]%MOD)
using namespace std;
typedef long long LL;
const int maxn=2e5+5;
const LL MOD=998244353;
LL ksm(LL a,LL b,LL mod)
{
    LL res=1,base=a;
    while(b)
    {
        if(b&1)res=(res*base)%mod;
        base=(base*base)%mod;
        b>>=1;
    }
    return res;
}
LL fac[maxn]={1,1},invf[maxn]={1,1};
void InitFac(int n)
{
    for(int i=2;i<=n;i++)fac[i]=fac[i-1]*i%MOD;
    invf[n]=ksm(fac[n],MOD-2,MOD);
    for(int i=n-1;i>=2;i--)invf[i]= invf[i+1]*(i+1)%MOD;
}
int main()
{
    InitFac(maxn-5);
    LL T,N,M,K;
    cin>>T;
    while(T--)
    {
        cin>>N>>M>>K;
        LL ans=0;
        for(LL c=0;c*N<=K;c++)
        {
            if(c>M)continue;//如果c大于M就是0 
            LL tp=C(M,c)*C(K-c*N+M-1,M-1)%MOD;
            if(c&1LL)ans-=tp;
            else ans+=tp;
            ans=(ans%MOD+MOD)%MOD;
        }
        cout<<ans<<endl;
    }
}

Taotao Picks Apples(hdu 6406)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6406
参考这位童鞋的博客：http://www.cnblogs.com/zzqc/p/9490772.html

思路：就是处理一个前缀 d1[i] $d1\left[i\right]$表示从 [1,i] $[1,i]$ 的答案，后缀 d2[i] $d2\left[i\right]$ 表示 [i,N] $[i,N]$ 的答案
加入现在修改 pos $pos$ 这个位置修改成 v $v$，设 t1 $t1$ 是 [1,pos−1] $[1,pos-1]$ 最大值的下标，那么前半段的答案就是 d1[t1] $d1\left[t1\right]$ ，因为我们是按照贪心来取数的，比上一次大的就一定会取，而不是求 LIS $LIS$ ，而后半段是要找第一个比 max(v,a[t1) $max(v,a[t1)$ 大的数，怎么样快速找到 第一个大的数呢？方法很多，这里是二分来找的

//ST表
#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;
const int inf=1e9;
int d1[maxn];//前缀
int d2[maxn];//后缀
int dp[maxn][20];//存区间内最大值的下标
int a[maxn];
int que[maxn];
int query(int L,int R)
{
    if(L>R)return 0;//正好d1[0]=d2[0]=0;
    int k=0;
    while((1<<(k+1))<R-L+1)k++;
    int t1=dp[L][k],t2=dp[R-(1<<k)+1][k];
    if(a[t1]>a[t2])return t1;
    else return t2;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        memset(d1,0,sizeof d1);
        memset(d2,0,sizeof d2);
        int N,Q;
        scanf("%d%d",&N,&Q);
        a[0]=-1e9,a[N+1]=1e9; 
        int Max=-1e9,cnt=0;
        for(int i=1; i<=N; i++)
        {
            scanf("%d",&a[i]);
            dp[i][0]=i;
            if(a[i]>Max)
            {
                Max=a[i];
                d1[i]=d1[i-1]+1;
            }
            else d1[i]=d1[i-1];
        }

        int tail=0,top=1;
        for(int i=N; i>=1; i--)//单调栈用来找后缀 
        {
            while(tail>=top&&a[i]>=a[que[tail]])tail--;
            que[++tail]=i;
            d2[i]=tail-top+1;
        }

        for(int j=1; (1<<j)<=N; j++)//ST表 
        {
            for(int i=1; i+(1<<j)-1<=N; i++)
            {
                int t1=dp[i][j-1],t2=dp[i+(1<<(j-1))][j-1];
                if(a[t1]>a[t2])dp[i][j]=t1;
                else dp[i][j]=t2;
            }
        }

        while(Q--)
        {
            int pos,v;
            scanf("%d%d",&pos,&v);
            int t1=query(1,pos-1),t2;

            //二分来找第一个大于的数 
            int l=pos+1,r=N,mid;
            while(l<=r)
            {
                mid=l+r>>1;
                if(a[query(l,mid)]>max(v,a[t1]))r=mid-1;
                else l=mid+1;
            }


            t2=l;
            int flag=0;
            if(a[t1]<v&&v<a[t2])flag=1;
            cout<<d1[t1]+flag+d2[t2]<<endl;
        }

    }
}