hihocoder 1882 播放列表 【容斥/DP】

全网就俩博文，，都没啥注释，，懂不起，去牛客群一问，炸出DP是自家学长写的，问到了，第二天补容斥，发现另一篇也是自家学长，好，又问，搞懂了。

学长太强了趴；

小Hi的手机中存着N首他喜爱的歌曲。现在小Hi希望制作一个长度为L的播放列表，满足

1. 每一首歌至少播放一编
2. 同一首歌不能连续播放，之间至少间隔一首其他歌曲

请你计算一共有多少种不同的播放列表满足条件？由于结果可能非常大，你只需要输出结果模1000000009的余数。

Input

两个整数N和L。

对于30%的数据，1 ≤ N ≤ 5，N ≤ L ≤ 10

对于100%的数据，1 ≤ N ≤ 1000, N ≤ L ≤ 2000

Output

一个整数，代表答案。

Sample Input

3 4

Sample Output

18

先上DP，DPNB！

174ms好强啊！

这里dp代表【列表能选】【选了几首】的方案数

原文链接

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define _for(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
typedef long long ll;
ll n, l;
ll dp[2007][2007];
const ll mod = 1e9 + 9;
int main() {
    while(~scanf("%lld %lld", &n, &l)) {
        memset(dp, 0, sizeof dp);
        dp[1][1] = n;
        _for(i, 1, l - 1) {
            _for(j, 1, n) {
                dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * (j - 1) % mod) % mod;
                //代表【i+1列表】【没多选】，所以*（j-1）就是可能数，因为相邻不同
                dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j] * (n - j) % mod) % mod;
                //又多选了一本，可能性就是*（n-j）
            }
        }
        printf("%lld\n", dp[l][n]);
    }
    return 0;
}
           

容斥的。。。居然0ms跑完了！

什么神仙代码哦。。。

先求阶乘，算组合数用，组合数的时候用了**

乘法逆元

**

先是取n-i首歌，第一个位置有n-i种，然后不相邻，就得*n-i-1，乘l-1个，所以是l-1次方。

具体用了容斥，可以简单了解下原理

原文链接

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define _for(i,a,b) for(ll i=(a);i<=(b);i++)
using namespace std;
typedef long long ll;
ll n, l;
const ll mod = 1e9 + 9;
ll jie[1007];
void pre() {
    jie[0] = jie[1] = 1;
    _for(i, 2, 1005)jie[i] = jie[i - 1] * i % mod;
}
ll quick(ll a, ll b, ll m) {
    ll ans = 1;
    while(b) {
        if(b & 1)
            ans = ans * a % m;
        a *= a;
        a %= m;
        b >>= 1;
    }
    return ans;
}
ll c(ll n, ll m) {
    return jie[n] * quick(jie[m], mod - 2, mod) % mod * quick(jie[n - m], mod - 2, mod) % mod;
}
int main() {
    pre();
    while(~scanf("%lld %lld", &n, &l)) {
        ll ans = 0;
        _for(i, 0, n - 1)
        ans = ( ans + ( ((i & 1) == 0) ? 1 : (-1)) * c(n, n - i) * (n - i) % mod * quick(n - i - 1, l - 1,mod) % mod + mod ) % mod;
        printf("%lld\n", ans);
    }
    return 0;
}