CF932E Team Work

2022-09-22 20:02:39 字數 1334 閱讀 2705

cf932e team work

講道理不難,但是我推不出來(指在模數為998244353的情況下的 \(o(k)\) 做法)我只能搞出 \(o (k \log n)\) 的,但是需要模數為998244353(你要用fft也行,不保證精度)。

那麼考慮 \(o(k^2)\)。顯然,你只需要 這題 就行了。 (推導過程容易發現 \(j \gt k\) 和 \(j=0\) 時,值為0。

\[\sum_^n \binom n i i^k \\

= \sum_^n \binom n i \sum_^i j! \binom i j \\

= \sum_^k j! \sum_^n \binom n i \binom i j\\

= \sum_^k j! \sum_^n \binom n j \binom \\

= \sum_^k j! \binom n j \sum_^n \binom \\

= \sum_^k j! \binom n j 2^

\]這題就可以 \(o(k^2)\) 完成了。但是我們怎麼可以放棄(大霧),我們已知

\[\\

= \frac \sum_^k (-1)^i \binom ki (k-i)^n \\

= \sum_^k \frac \frac

\]那麼我們可以直接卷一下就變成 \(o (k \log n)\) 了(模數998244353)。

\(o(k)\) 做法請去看min_25部落格。

/*

name:

author: gensokyo_alice

date:

description:

*/#include #include #include #include #include #include #include #include #include #include #include using namespace std;

typedef long long ll;

const ll maxn = (1ll << 20) + 10, mod = 1e9+7, inf = 0x3f3f3f3f3f3f3f3f;

ll n, k, ans, fac[maxn], inv[maxn];

ll ks(ll, ll);

namespace subtask2

printf("%lld\n", ans);

}}int main()

return 0;

}ll ks(ll n, ll tim)

if (flag) return ks(ret, mod - 2);

return ret;

}

CF932E Team Work

problem 題意 求 sum n beginn i end times i k 大力頹柿子,根據常冪轉下降冪公式,有 sum n beginn i end times i k sum n beginn i end sum i begink j end times i sum n beginn i...

CF 932E Team Work

傳送門題意 求一個和式 sum n binom i k 這個時候我們需要推一下式子,我們把 i k 用第二類斯特林數展開 i k sum kj s k j binom sum n frac sum k frac sum ks k j sum n frac sum ks k j frac sum n ...

CF932E Team Work(第二類斯特林數)

傳送門 cf原網 洛谷題意 給定 n k ,求 sum limits n dbinomi k bmod 10 9 7 。 1 le n le 10 9 1 le k le 5000 。 很水的一道題。 根據第二類斯特林數的性質 n k sum k begink i endi dbinom 那麼直接套...