青岛网站制作工具,有做自由行包车的网站,做网站图片切图是什么,网络编程课题目链接
Atcoder方向 Luogu方向
题目解法
考虑满足条件 2 2 2 的形式为 a n p 0 ∑ i ∈ n p i a_np_0\sum\limits_{i\in n}p_i anp0i∈n∑pi 这是一步很巧妙的转化#xff0c;神奇地利用了 \ 和 ∣ | ∣ 的性质#xff0c;把求 a a a 的…题目链接
Atcoder方向 Luogu方向
题目解法
考虑满足条件 2 2 2 的形式为 a n p 0 ∑ i ∈ n p i a_np_0\sum\limits_{i\in n}p_i anp0i∈n∑pi 这是一步很巧妙的转化神奇地利用了 \ 和 ∣ | ∣ 的性质把求 a a a 的方案数转化为求 p p p 的方案数 考虑如何满足条件 1 1 1令 p i 0 p_i0 pi0 的和为 X X X p i 0 p_i0 pi0 的和为 Y Y Y那么 min { a i } X p 0 , max { a i } Y p 0 \min\{a_i\}Xp_0,\;\max\{a_i\}Yp_0 min{ai}Xp0,max{ai}Yp0 所以可以得出 − X ≤ p 0 ≤ k − Y -X\le p_0\le k-Y −X≤p0≤k−Y所以合法的 p 0 p_0 p0 取值有 k − ( Y − X ) 1 k-(Y-X)1 k−(Y−X)1 种 考虑 Y − X ∑ ∣ a i ∣ Y-X\sum |a_i| Y−X∑∣ai∣所以 k − ( Y − X ) − 1 k 1 − ∑ ∣ p i ∣ k-(Y-X)-1k1-\sum{|p_i|} k−(Y−X)−1k1−∑∣pi∣
考虑枚举 p p p 中非 0 0 0 的个数正负性有 2 i 2^i 2i 种 s s s 表示绝对值之和然后就是 s s s 个球分给 i i i 个盒子每个盒子不为空且要分完的方案数经典问题最后再乘上 p 0 p_0 p0 的取值方案数 所以 A n s ∑ i 0 n ( n i ) 2 i ∑ s i k 1 ( s − 1 i − 1 ) ( k 1 − s ) Ans\sum\limits_{i0}^{n}\binom{n}{i}2^i\sum\limits_{si}^{k1}\binom{s-1}{i-1}(k1-s) Ansi0∑n(in)2isi∑k1(i−1s−1)(k1−s) 只考虑 ∑ s i k 1 ( s − 1 i − 1 ) ( k 1 − s ) ∑ s i k 1 ( k 1 ) ( s − 1 i − 1 ) − s ( s − 1 i − 1 ) ( k 1 ) ( k 1 i ) − ∑ s i k 1 i ( s i ) ( k 1 ) ( k 1 i ) − i ( k 2 i 1 ) \sum\limits_{si}^{k1}\binom{s-1}{i-1}(k1-s)\\\sum\limits_{si}^{k1}(k1)\binom{s-1}{i-1}-s\binom{s-1}{i-1} \\(k1)\binom{k1}{i}-\sum\limits_{si}^{k1}i\binom{s}{i} \\(k1)\binom{k1}{i}-i\binom{k2}{i1} si∑k1(i−1s−1)(k1−s)si∑k1(k1)(i−1s−1)−s(i−1s−1)(k1)(ik1)−si∑k1i(is)(k1)(ik1)−i(i1k2) 展开然后化简这里就不细写了 最后化简出来是 A n s ∑ i 0 n ( n i ) 2 i ( k 1 i 1 ) Ans\sum\limits_{i0}^{n}\binom{n}{i}2^i\binom{k1}{i1} Ansi0∑n(in)2i(i1k1)
直接求解即可时间复杂度 O ( n ) O(n) O(n)
#include bits/stdc.h
#define int long long
using namespace std;
const int N300100,P998244353;
int n,k,fac[N],inv[N];
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
int qmi(int a,int b){int res1;for(;b;b1){if(b1) resres*a%P;aa*a%P;}return res;
}
int C(int a,int b){ return fac[a]*inv[b]%P*inv[a-b]%P;}
signed main(){nread(),kread();fac[0]1;for(int i1;in1;i) fac[i]fac[i-1]*i%P;inv[n1]qmi(fac[n1],P-2);for(int in;i0;i--) inv[i]inv[i1]*(i1)%P;int ans0,res(k1)%P;for(int i0,pw1;in;i,pwpw*2%P){ans(ansC(n,i)*pw%P*res%P*inv[i1])%P;resres*((k1-i-1)%P)%P;}printf(%lld,ans);return 0;
}
