F - Color

题目链接：http://codeforces.com/gym/100548/attachments
题意：给 N $N$ 个位置填颜色，且相邻的位置不能填同样的颜色，有 M $M$ 种颜色阔以选，问填 K $K$ 种颜色的方案数

我也不是很懂怎么容斥的T_T，大概就是说：
选出的这 K $K$ 种颜色，可能有 0 $0$ 种不填，可能有 1 $1$ 种不填，可能有 2 $2$ 种不填。。。。可能有 K−1 $K-1$ 种不填
换句话说就是：可能填 K $K$ 种，可能填 K−1 $K-1$ 种，可能填 K−2 $K-2$ 种。。。。可能填 1 $1$ 种
而我们要的就是可能填 K $K$ 种的，因此就把后面的容斥掉

i $i$ 种颜色不选的公式为： K $K$种颜色中哪 i $i$ 种颜色不选就是 CiK $C_K^i$ ，然后第一个位置有 K−i $K-i$种颜色阔以选，后面 N−1 $N-1$ 个位置因为不能与上一个颜色相同就只能选 K−1−i $K-1-i$ 种颜色，所以总共就是 CiK⋅(K−i)1⋅(K−1−i)N−1 $C_K^i\cdot (K-i{)}^1\cdot (K-1-i{)}^{N-1}$

然后就是后面容斥的时候，会频繁地用到 CiK $C_K^i$因此用递推式先预处理一哈，最后再乘一哈是在 M $M$ 种颜色中选的哪 K $K$ 种就行了，就是乘一个 CKM $C_M^K$

//#include"bits/stdc++.h"
#include"cstdio"
#include"iostream"
using namespace std;
const int maxn=1e6+5;
typedef long long LL;
const LL MOD=1e9+7;
LL N,M,K;
LL fac[maxn]= {1,1},inv[maxn]= {1,1},invf[maxn]= {1,1};
LL Ck[maxn]= {1};
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;
}
void Init(int n)
{
    for(int i=2; i<=n; i++)
    {
        fac[i]=fac[i-1]*i%MOD;
        inv[i]=(MOD-MOD/i)*inv[MOD%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;
}
LL C(LL n,LL m)
{
    m=min(m,n-m);
    LL res=1;
    for(LL i=n; i>n-m; i--)res=(res*i)%MOD;
    res=(res*invf[m])%MOD;
    return res;
}

int main()
{
    Init(maxn-5);
    int T;
    cin>>T;
    for(int Case=1; Case<=T; Case++)
    {
        scanf("%I64d%I64d%I64d",&N,&M,&K);
        cout<<"Case #"<<Case<<": ";
        for(LL i=1; i<=K; i++)Ck[i]=Ck[i-1]*(K-i+1)%MOD*inv[i]%MOD;//预处理C(K,i) 
        LL ans=0;
        for(LL i=0;i<K;i++)//表示有i种颜色不选 
        {
            LL tp=Ck[i]*(K-i)%MOD*ksm(K-1-i,N-1,MOD);
            if(i&1)ans-=tp;
            else ans+=tp;
            ans%=MOD;
        }
        ans=(C(M,K)*ans%MOD+MOD)%MOD;
        cout<<ans<<endl;
    }
}

I - International Collegiate Routing Contest

题目链接：http://codeforces.com/gym/100548/attachments
参考这位童鞋的博客：https://blog.csdn.net/u013849646/article/details/52238850
题意：说一哈样例是啥意思，比如第二个 0.0.0.0/1 $\mathrm{0.0.0.0}/1$，前面四个数就是表示子网掩码啥的，反正就是个 0 $0$~ 255 $255$ 的一个数，关键是斜杠后面的，表示前面这么多位是不能动的，后面的位随便变，然后问还需要哪些才能把所有的地址覆盖完
比如要是斜杠后面的是 0 $0$ 说明前 0 $0$ 位不能变，其他的都能变，那相当于所有的数都能随便变，那不就把所有的地址都覆盖完了么，所以答案就是还需要添加 0 $0$ 种，而样例是前 1 $1$ 位固定为 0 $0$ ，所以还需要前 1 $1$ 位是 1 $1$ 的随便变就行了

第二个样例就是固定了前 1 $1$ 位，并且他是 128 $128$ 转换成 2 $2$ 进制就是 10000000 $10000000$，第一位就是 1 $1$ ，因此还需要添加第一位是 0 $0$ 的，后面随便变的就行了

然后这题的思路就是把每个地址都转换成 2 $2$ 进制然后放进字典树里面，这道题要是给我说了字典树我也很无语，因为那后面随便变的我不知道怎么处理，而这题很机智的就是在固定不动的最后一位那里打个标记，相当于说是个单词结尾，而查找的时候，遇到打标记的地方就停了，哇我感觉这个很机智

然后代码最关键的地方就是查找答案的时候，查找函数是有返回值的，返回值为 1 $1$ 表示有这条路，返回值为 0 $0$ 表示没有这条路，那我们就需要添加这条路，并且把地址映射的值和走了几层记录下来，这个映射的值是倒着来的，也就是说固定的那几位是在低位，到时候转换成地址的时候弄一哈就是了

这个地址映射的值感觉有点不好怎，本来想从高位到低位正常的这样赋值的，但是不好继承上一次的value

#include"bits/stdc++.h"
using namespace std;
const int maxn=1e6+5;
typedef long long LL;
int ch[maxn<<5][2],vis[maxn<<5];
vector<pair<LL,int> >Ans;
int tot;
void Insert(LL v,int lim)
{
    int u=0;
    for(int i=31;i>=32-lim;i--)
    {
        int c=1&(v>>i);
        if(ch[u][c]==-1)
        {
            ch[u][c]=++tot;
            vis[tot]=0;
        }
        u=ch[u][c];
    }
    vis[u]=1;//表示一个单词的末尾 
}
int query(int u,LL v,int lim)//lim表示走到了第几层，也是表示前lim位是固定的 
{
    if(u==-1)return 0;//没有儿子了，说明这条路走到头了 
    if(vis[u])return vis[u];//如果找到个单词的末尾，那么他后面的都是阔以覆盖的，说明肯定有路，就直接返回1了 
    if(lim==32)return vis[u];
    int p1=query(ch[u][0],v<<1,lim+1);
    int p2=query(ch[u][1],v<<1|1,lim+1);
    if(p1&&p2==0)//如果右边没有路，那么右边就是一个答案 
    {
        Ans.push_back(make_pair(v<<1|1,lim+1)); 
    }
    else if(p1==0&&p2)
    {
        Ans.push_back(make_pair(v<<1,lim+1));
    }
    return p1|p2;//两条路中有一条就行，就说明说阔以往下继续走的 
}
void print(LL v,int lim)
{
    v<<=32-lim;
    int t1=(v>>24);
    int t2=(v>>16)^(t1<<8);
    int t3=(v>>8)^(t1<<16)^(t2<<8);
    int t4=v^(t1<<24)^(t2<<16)^(t3<<8);
    cout<<t1<<"."<<t2<<"."<<t3<<"."<<t4<<"/"<<lim<<endl;
}
int main()
{
    int T;
    cin>>T;
    for(int Case=1;Case<=T;Case++) 
    {
        tot=0;
        Ans.clear();
        memset(ch,-1,sizeof ch);
        memset(vis,0,sizeof vis);
        int N;
        cin>>N;
        for(int i=1;i<=N;i++)
        {
            LL t1,t2,t3,t4;
            int lim;
            scanf("%lld.%lld.%lld.%lld/%d",&t1,&t2,&t3,&t4,&lim);
            LL v=(t1<<24)+(t2<<16)+(t3<<8)+t4;
            Insert(v,lim);
        }
        cout<<"Case #"<<Case<<":"<<endl;
        if(N==0)
        {
            cout<<1<<endl;
            cout<<"0.0.0.0/0"<<endl;
            continue;
        }
        query(0,0,0);
        cout<<Ans.size()<<endl;
        for(int i=0;i<Ans.size();i++)
        {
            print(Ans[i].first,Ans[i].second);
        }
    }
}