题解 P2768 【珍珠项链】

YouAreMySunshine · 2016-11-10 17:21:54 · 题解

//看到大神们都不愿写题解那我就来补一发题解好了…… 写的不好或者有问题欢迎指正

• 看完题之后首先观察一下数据范围，N<=100000000,时限10ms ,然后T和k非常的小，这启发我们想一个和log n有关的算法

• 仔细审题，题目中 组成多少种长度为1至N的不同的珍珠垂饰，每串珍珠垂饰都要必须由K种珍珠连成 这告诉我们合法的项链长度至少为K，要求的就是长度K到N的项链中 用了K种珍珠的项链数 ( 以下提到的项链均指长度为K到N的项链 )

• 先考虑不要求一定要用完K种珍珠的项链数 。 显然正好用i种珍珠形成的所有项链有

  g[i]=i^k+i^(k+1)+i^(k+2)+i^(k+3) ··· +i^n种

• 设f[i]为正好有i种珍珠可形成的所有合法的项链数 那么本题答案即为f[k] 那f[i]应该怎么算呢？ 运用容斥原理 合法的项链数=总项链数-非法项链数（即没有用够i种珍珠的项链） ，那么我们可以找到关于f数组的递推关系

可以得出这样一个结论：对于 f[i] , 所有 f[j] (1<=j<i )，都是非法的

然而因为种类增加了 所以并不能单纯地减掉f[j]，而应该减去 f[j]*C( j , i ) （因为从i种中选j种种类有C（j，i）种方案）

于是 f[i] = g[i]-f[j]*C(j,i) (1<=j<i ) f[0]=0

于是就能递推地计算出f[k] 注意g[i]的计算要用等比数列求和公式 以及组合数的计算要求逆元 （都是一个快速幂的事儿） 还有就是最好变量和函数返回值都开long long 因为MOD+MOD>2147483647 以及int的自乘会溢出啥的

• 总复杂度O（T（k^2+klogn））常数还挺小 足够在10ms之内出解啦

（我由于懒没写组合数的预处理，所以我程序的复杂度实际是O（T（k^3+klogn））的，香港记者号太劲了还是能1ms出解）

• 代码仅供参考：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
    using namespace std;
const int MOD=1234567891;
ll f[33],f1[33];
int Inv[33];
int t,n,k;

ll fpower(ll a,ll b){
    ll r=1,c=b;
    while (c) {
        if (c&1) r=r*a%MOD;
        a=a*a%MOD;
        c>>=1;
    }
    return r;
}

inline ll C(int up,int down) {
    ll res=1;
    if (up==down) return 1;
    if (up>(down-up)) up=down-up;
    for (int i=down-up+1;i<=down;i++) res=res*i%MOD;
    for (int i=1;i<=up;i++) res=res*Inv[i]%MOD;
    return res;
}

int main(){
    cin>>t;
    for (int i=1;i<=30;i++) Inv[i]=fpower(i,MOD-2);
    while (t--) {
        scanf("%d%d",&n,&k);
        f[0]=0; f[1]=n-k+1;
        for (int i=2;i<=k;i++) {
            f[i]=(((fpower(i,n+1)-fpower(i,k)+MOD)%MOD)*Inv[i-1])%MOD;
            for (int j=1;j<i;j++) 
                f[i]=(f[i]-f[j]*C(j,i)%MOD+MOD)%MOD;
        }
        cout<<f[k]<<endl;
    }
    return 0;
}