题单:https://codeforces.com/problemset?tags=combinatorics,1201-1600
原题指路:https://codeforces.com/problemset/problem/1096/B
给定一个长度为 n ( 2 ≤ n ≤ 2 e 5 ) n\ \ (2\leq n\leq 2\mathrm{e}5) n (2≤n≤2e5)的只包含小写英文字母且至少包含两种字符的字符串 s s s.现有操作:删除一个 s s s的非空子串,使得剩下的字符都相同,注意删除整个 s s s也是合法的.求合法的操作数,答案对 998244353 998244353 998244353取模.
显然最后剩下的字符串是 s s s的某个前缀或后缀.设 s s s有长度为 l l l的与首字符相同的前缀和长度为 r r r的与尾字符相同的后缀.
① s 1 ≠ s n s_1\neq s_n s1=sn时,若保留与首字符相同的字符,则需删除长度为 l l l的前缀的某个字符之后的所有字符,有 l l l种情况.
同理保留与尾字符相同的字符有 r r r种情况,再加上删除整个 s s s,则 a n s = l + r + 1 ans=l+r+1 ans=l+r+1.
② s 1 = s n = c h s_1=s_n=ch s1=sn=ch时,因 s s s至少包含两种字符,则与首字符相同的前缀和与尾字符相同的后缀不相交.
对前缀的 l l l个 c h ch ch,可保留 [ 0 , l ] [0,l] [0,l]个,有 ( l + 1 ) (l+1) (l+1)种情况,同理右边有 ( r + 1 ) (r+1) (r+1)种情况,则 a n s = ( l + 1 ) ( r + 1 ) ans=(l+1)(r+1) ans=(l+1)(r+1).
const int MOD = 998244353;
void solve() {
int n; string s; cin >> n >> s;
int l = 0, r = 0;
for (int i = 0; i < n; i++) {
if (s[i] == s[0]) l++;
else break;
}
for (int i = n - 1; i >= 0; i--) {
if (s[i] == s[n - 1]) r++;
else break;
}
cout << (s[0] == s[n - 1] ? (ll)(l + 1) * (r + 1) % MOD : (l + r + 1) % MOD);
}
int main() {
solve();
}
原题指路:https://codeforces.com/problemset/problem/1105/C
给定三个整数 n , l , r ( 1 ≤ n ≤ 2 e 5 , 1 ≤ l ≤ r ≤ 1 e 9 ) n,l,r\ \ (1\leq n\leq 2\mathrm{e}5,1\leq l\leq r\leq 1\mathrm{e}9) n,l,r (1≤n≤2e5,1≤l≤r≤1e9),求满足如下性质的整数序列 a 1 , ⋯ , a n a_1,\cdots,a_n a1,⋯,an的个数,答案对 1 e 9 + 7 1\mathrm{e}9+7 1e9+7取模:① a i ∈ [ l , r ] ( 1 ≤ i ≤ n ) a_i\in[l,r]\ \ (1\leq i\leq n) ai∈[l,r] (1≤i≤n);② 3 ∣ ∑ i = 1 n a i 3\bigg|\displaystyle\sum_{i=1}^n a_i 3∣ ∣i=1∑nai.
显然只需考虑 x ∈ [ l , r ] x\in [l,r] x∈[l,r]模 3 3 3的结果.以模 3 3 3余 1 1 1为例,令 x = 3 k + 1 ∈ [ l , r ] x=3k+1\in [l,r] x=3k+1∈[l,r],解得 ⌈ l − 1 3 ⌉ ≤ k ≤ ⌊ r − 1 3 ⌋ \left\lceil\dfrac{l-1}{3}\right\rceil\leq k\leq \left\lfloor\dfrac{r-1}{3}\right\rfloor ⌈3l−1⌉≤k≤⌊3r−1⌋.同理可求得区间内模 3 3 3余 0 , 2 0,2 0,2的数的个数.分别设区间内模 3 3 3余 0 , 1 , 2 0,1,2 0,1,2的数的个数为 c n t 0 , c n t 1 , c n t 2 cnt_0,cnt_1,cnt_2 cnt0,cnt1,cnt2.
d p [ i ] [ j ] dp[i][j] dp[i][j]表示前 i i i个数之和模 3 3 3余 j j j的方案数,则 a n s = d p [ n ] [ 3 ] ans=dp[n][3] ans=dp[n][3].
状态转移方程: { d p [ i ] [ 0 ] = d p [ i − 1 ] [ 0 ] ∗ c n t 0 + d p [ i − 1 ] [ 1 ] ∗ c n t 2 + d p [ i − 1 ] [ 2 ] ∗ c n t 1 d p [ i ] [ 1 ] = d p [ i − 1 ] [ 0 ] ∗ c n t 1 + d p [ i − 1 ] [ 1 ] ∗ c n t 0 + d p [ i − 1 ] [ 2 ] ∗ c n t 2 d p [ i ] [ 2 ] = d p [ i − 1 ] [ 0 ] ∗ c n t 2 + d p [ i − 1 ] [ 1 ] ∗ c n t 1 + d p [ i − 1 ] [ 2 ] ∗ c n t 0 \begin{cases}dp[i][0]=dp[i-1][0]*cnt_0+dp[i-1][1]*cnt_2+dp[i-1][2]*cnt_1 \\ dp[i][1]=dp[i-1][0]*cnt_1+dp[i-1][1]*cnt_0+dp[i-1][2]*cnt_2 \\ dp[i][2]=dp[i-1][0]*cnt_2+dp[i-1][1]*cnt_1+dp[i-1][2]*cnt_0\end{cases} ⎩ ⎨ ⎧dp[i][0]=dp[i−1][0]∗cnt0+dp[i−1][1]∗cnt2+dp[i−1][2]∗cnt1dp[i][1]=dp[i−1][0]∗cnt1+dp[i−1][1]∗cnt0+dp[i−1][2]∗cnt2dp[i][2]=dp[i−1][0]∗cnt2+dp[i−1][1]∗cnt1+dp[i−1][2]∗cnt0.
初始条件 d p [ 0 ] [ 0 ] = 1 dp[0][0]=1 dp[0][0]=1.
const int MAXN = 2e5 + 5;
const int MOD = 1e9 + 7;
int n, l, r;
int dp[MAXN][3]; // dp[i][j]表示前i个数之和模3余j的方案数
void solve() {
cin >> n >> l >> r;
// [l,r]内模3余0,1,2的数的个数
int cnt0 = (r + 3) / 3 - (l + 2) / 3, cnt1 = (r + 2) / 3 - (l + 1) / 3, cnt2 = (r + 1) / 3 - l / 3;
dp[0][0] = 1; // 初始条件
for (int i = 1; i <= n; i++) {
dp[i][0] = ((ll)dp[i - 1][0] * cnt0 % MOD + (ll)dp[i - 1][1] * cnt2 % MOD + (ll)dp[i - 1][2] * cnt1 % MOD) % MOD;
dp[i][1] = ((ll)dp[i - 1][0] * cnt1 % MOD + (ll)dp[i - 1][1] * cnt0 % MOD + (ll)dp[i - 1][2] * cnt2 % MOD) % MOD;
dp[i][2] = ((ll)dp[i - 1][0] * cnt2 % MOD + (ll)dp[i - 1][1] * cnt1 % MOD + (ll)dp[i - 1][2] * cnt0 % MOD) % MOD;
}
cout << dp[n][0];
}
int main() {
solve();
}
上述状态转移方程可写成矩阵的形式:
[ d p [ i − 1 ] [ 0 ] d p [ i − 1 ] [ 1 ] d p [ i − 1 ] [ 2 ] ] [ c n t 0 c n t 1 c n t 2 c n t 2 c n t 0 c n t 1 c n t 1 c n t 2 c n t 0 ] = [ d p [ i ] [ 0 ] d p [ i ] [ 1 ] d p [ i ] [ 2 ] ] \begin{bmatrix}dp[i-1][0]& dp[i-1][1]& dp[i-1][2]\end{bmatrix}\begin{bmatrix}cnt_0 & cnt_1 & cnt_2 \\ cnt_2 & cnt_0 & cnt_1 \\ cnt_1 & cnt_2 & cnt_0\end{bmatrix}=\begin{bmatrix}dp[i][0]& dp[i][1]& dp[i][2]\end{bmatrix} [dp[i−1][0]dp[i−1][1]dp[i−1][2]]⎣ ⎡cnt0cnt2cnt1cnt1cnt0cnt2cnt2cnt1cnt0⎦ ⎤=[dp[i][0]dp[i][1]dp[i][2]].
矩阵快速幂即可.
const int MAXN = 2e5 + 5;
const int MOD = 1e9 + 7;
int n, l, r;
template<typename T>
struct Matrix {
static const int MAXSIZE = 5;
int n, m; // 行数、列数
T a[MAXSIZE][MAXSIZE]; // 下标从1开始
Matrix() :n(0), m(0) { memset(a, 0, so(a)); }
Matrix(int _n, int _m) :n(_n), m(_m) { memset(a, 0, so(a)); }
void init_identity() { // 初始化为单位矩阵
assert(n == m);
memset(a, 0, so(a));
for (int i = 1; i <= n; i++) a[i][i] = 1;
}
Matrix<T> operator+(const Matrix<T>& B)const {
assert(n == B.n), assert(m == B.m);
Matrix<T> res(n, n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
res.a[i][j] = ((ll)a[i][j] + B.a[i][j]) % MOD;
}
return res;
}
Matrix<T> operator-(const Matrix<T>& B)const {
assert(n == B.n), assert(m == B.m);
Matrix<T> res(n, n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
res.a[i][j] = ((a[i][j] - B.a[i][j]) % MOD + MOD) % MOD;
}
return res;
}
Matrix<T> operator*(const Matrix<T>& B)const {
assert(m == B.n);
Matrix<T> res(n, B.m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= B.m; j++) {
for (int k = 1; k <= m; k++)
res.a[i][j] = ((ll)res.a[i][j] + (ll)a[i][k] * B.a[k][j]) % MOD;
}
}
return res;
}
Matrix<T> operator^(int k)const { // 快速幂
assert(n == m);
Matrix<T> res(n, n);
res.init_identity(); // 单位矩阵
Matrix<T> tmpa(n, n); // 存放矩阵a[][]的乘方
memcpy(tmpa.a, a, so(a));
while (k) {
if (k & 1) res = res * tmpa;
k >>= 1;
tmpa = tmpa * tmpa;
}
return res;
}
Matrix<T>& operator=(const Matrix<T>& B) {
memset(a, 0, so(a));
n = B.n, m = B.m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) a[i][j] = B.a[i][j];
return *this;
}
bool operator==(const Matrix<T>& B)const {
if (n != B.n || m != B.m) return false;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
if (a[i][j] != B.a[i][j]) return false;
}
return true;
}
void print() {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) cout << a[i][j] << " \n"[j == m];
}
};
void solve() {
cin >> n >> l >> r;
// [l,r]内模3余0,1,2的数的个数
int cnt0 = (r + 3) / 3 - (l + 2) / 3, cnt1 = (r + 2) / 3 - (l + 1) / 3, cnt2 = (r + 1) / 3 - l / 3;
Matrix<int> ans(3, 3);
ans.a[1][1] = 1; // dp[0][0]=1
Matrix<int> trans(3, 3);
trans.a[1][1] = trans.a[2][2] = trans.a[3][3] = cnt0;
trans.a[1][2] = trans.a[2][3] = trans.a[3][1] = cnt1;
trans.a[1][3] = trans.a[2][1] = trans.a[3][2] = cnt2;
ans = ans * (trans ^ n);
cout << ans.a[1][1]; // dp[n][0]
}
int main() {
solve();
}
原题指路:https://codeforces.com/problemset/problem/1178/C
现有如上图所示的 1 × 1 1\times 1 1×1的正方形砖块,每块砖可任意旋转.先要用砖铺满 w × h ( 1 ≤ w , h ≤ 1000 ) w\times h\ \ (1\leq w,h\leq 1000) w×h (1≤w,h≤1000)的地面,要求每条边两侧的三角形的颜色不同,如下图左图是一种合法的方案,而右图不合法,求方案数,答案对 998244353 998244353 998244353取模.
①当一个格子的四周有 0 0 0个确定的格子时,该格子有 4 4 4种选择.
②当一个格子的四周有 1 1 1个确定的格子时,该格子有 2 2 2种选择.
③当一个格子的四周有 2 2 2个确定的格子时,该格子有 1 1 1种选择.
先确定 w × h w\times h w×h的网格左上角的格子,有 4 4 4种选择,第一行剩余的格子都有 2 2 2种选择,第一列剩余的格子也都有 2 2 2种选择.确定第一行和第一列的格子后,整个网格唯一确定,故 a n s = 4 ⋅ 2 w − 1 ⋅ 2 h − 1 = 2 w + h ans=4\cdot 2^{w-1}\cdot 2^{h-1}=2^{w+h} ans=4⋅2w−1⋅2h−1=2w+h.
const int MOD = 998244353;
void solve() {
int w, h; cin >> w >> h;
cout << qpow(2, w + h, MOD);
}
int main() {
solve();
}
原题指路:https://codeforces.com/problemset/problem/1195/D1
给定两个整数的十进制表示(无前导零) a 1 , ⋯ , a p a_1,\cdots,a_p a1,⋯,ap和 b 1 , ⋯ , b q b_1,\cdots,b_q b1,⋯,bq.定义函数 f ( a 1 , ⋯ , a p , b 1 , ⋯ , b q ) = { a 1 a 2 ⋯ a p − q + 1 b 1 a p − q + 2 b 2 ⋯ a p − 1 b q − 1 a p b q , p ≥ q b 1 b 2 ⋯ b q − p a 1 b q − p + 1 a 2 ⋯ a p − 1 b q − 1 a p b q , p < q f(a_1,\cdots,a_p,b_1,\cdots,b_q)=\begin{cases}a_1a_2\cdots a_{p-q+1} b_1 a_{p-q+2}b_2\cdots a_{p-1} b_{q-1}a_p b_q,p\geq q \\ b_1b_2 \cdots b_{q-p} a_1 b_{q-p+1}a_2\cdots a_{p-1}b_{q-1}a_p b_q,p<q\end{cases} f(a1,⋯,ap,b1,⋯,bq)={a1a2⋯ap−q+1b1ap−q+2b2⋯ap−1bq−1apbq,p≥qb1b2⋯bq−pa1bq−p+1a2⋯ap−1bq−1apbq,p<q.如 f ( 1111 , 2222 ) = 12121212 , f ( 7777 , 888 ) = 7787878 , f ( 111 , 2222 ) = ( 2121212 ) f(1111,2222)=12121212,f(7777,888)=7787878,f(111,2222)=(2121212) f(1111,2222)=12121212,f(7777,888)=7787878,f(111,2222)=(2121212).
给定一个长度为 n ( 1 ≤ n ≤ 1 e 5 ) n\ \ (1\leq n\leq 1\mathrm{e}5) n (1≤n≤1e5)的序列 a 1 , ⋯ , a n ( 1 ≤ a i ≤ 1 e 9 ) a_1,\cdots,a_n\ \ (1\leq a_i\leq 1\mathrm{e}9) a1,⋯,an (1≤ai≤1e9),其中每个 a i a_i ai的十进制表示(无前导零)等长.求 ∑ i = 1 n ∑ j = 1 n f ( a i , a j ) \displaystyle \sum_{i=1}^n \sum_{j=1}^n f(a_i,a_j) i=1∑nj=1∑nf(ai,aj),答案对 998244353 998244353 998244353取模.
显然有 f ( a i , a j ) f(a_i,a_j) f(ai,aj)也会有 f ( a j , a i ) f(a_j,a_i) f(aj,ai).因每个 a i a_i ai的十进制表示等长,注意到 f ( a 1 ⋯ a p , b 1 ⋯ , b p ) = a 1 b 1 a 2 b 2 ⋯ b p b p , f ( b 1 ⋯ , b p , a 1 ⋯ a p ) = b 1 a 1 b 2 a 2 ⋯ b p a p f(a_1\cdots a_p,b_1\cdots,b_p)=a_1b_1a_2b_2\cdots b_pb_p,f(b_1\cdots,b_p,a_1\cdots a_p)=b_1a_1b_2a_2\cdots b_p a_p f(a1⋯ap,b1⋯,bp)=a1b1a2b2⋯bpbp,f(b1⋯,bp,a1⋯ap)=b1a1b2a2⋯bpap,即 f ( a i , a j ) + f ( a j , a i ) = f ( a i , a i ) + f ( a j , a j ) f(a_i,a_j)+f(a_j,a_i)=f(a_i,a_i)+f(a_j,a_j) f(ai,aj)+f(aj,ai)=f(ai,ai)+f(aj,aj),则 ∑ i = 1 n ∑ j = 1 n f ( a i , a j ) = n ∑ i = 1 n f ( a i , a i ) \displaystyle \sum_{i=1}^n \sum_{j=1}^n f(a_i,a_j)=n\sum_{i=1}^n f(a_i,a_i) i=1∑nj=1∑nf(ai,aj)=ni=1∑nf(ai,ai).
const int MOD = 998244353;
void solve() {
int n; cin >> n;
int ans = 0;
for (int i = 0; i < n; i++) {
string s; cin >> s;
int len = s.length();
int cur = 0;
for (int i = 0; i < len; i++) {
cur = ((ll)cur * 10 + s[i] - '0') % MOD;
cur = ((ll)cur * 10 + s[i] - '0') % MOD;
}
ans = (ans + cur) % MOD;
}
ans = (ll)ans * n % MOD;
cout << ans;
}
int main() {
solve();
}
原题指路:https://codeforces.com/problemset/problem/1215/B
给定一个长度为 n ( 1 ≤ n ≤ 2 e 5 ) n\ \ (1\leq n\leq 2\mathrm{e}5) n (1≤n≤2e5)的序列 a 1 , ⋯ , a n ( − 1 e 9 ≤ a i ≤ 1 e 9 , a i ≠ 0 ) a_1,\cdots,a_n\ \ (-1\mathrm{e}9\leq a_i\leq 1\mathrm{e}9,a_i\neq 0) a1,⋯,an (−1e9≤ai≤1e9,ai=0).求:(1)满足 a l × ⋯ × a r < 0 a_l\times \cdots\times a_r<0 al×⋯×ar<0的区间 [ l , r ] [l,r] [l,r]的个数;(2)满足 a l × ⋯ × a r > 0 a_l\times \cdots\times a_r>0 al×⋯×ar>0的区间 [ l , r ] [l,r] [l,r]的个数.
显然可将正数都视为 1 1 1,负数都视为 − 1 -1 −1.显然只需计算(1)的答案 a n s ans ans,则(2)的答案为 n ( n + 1 ) 2 − a n s \dfrac{n(n+1)}{2}-ans 2n(n+1)−ans.
维护前缀积 p r e [ ] pre[] pre[],初始时 p r e [ 0 ] = 1 pre[0]=1 pre[0]=1.枚举到每个 a i a_i ai时,若当前 p r e [ i ] > 0 pre[i]>0 pre[i]>0,则满足(1)的区间数即之前使得 p r e [ j ] < 0 pre[j]<0 pre[j]<0的 j ( j < i ) j\ \ (j<i) j (j<i)的个数,累加至答案即可.
void solve() {
int pre = 1; // 前缀积
int pos = 1, neg = 0; // 已求出的前缀积中>0、<0的个数
ll ans = 0;
int n; cin >> n;
for (int i = 0; i < n; i++) {
int a; cin >> a;
pre *= a > 0 ? 1 : -1;
ans += pre > 0 ? neg : pos;
if (pre > 0) pos++;
else neg++;
}
cout << ans << ' ' << (ll)n * (n + 1) / 2 - ans;
}
int main() {
solve();
}
原题指路:https://codeforces.com/problemset/problem/1236/B
将 n ( 1 ≤ n ≤ 1 e 9 ) n\ \ (1\leq n\leq 1\mathrm{e}9) n (1≤n≤1e9)种物品放入 m ( 1 ≤ m ≤ 1 e 9 ) m\ \ (1\leq m\leq 1\mathrm{e}9) m (1≤m≤1e9)个不同的盒子中,要求:①每个盒子中不能出现相同的物品;②在 m m m个背包中所有 n n n种物品都出现过;③允许有空盒子.求方案数,答案对 1 e 9 + 7 1\mathrm{e}9+7 1e9+7取模.
对一种物品,将其放在 m m m个不同的盒子中有 2 m − 1 2^m-1 2m−1种方案.显然每种物品的放置独立,故 a n s = ( 2 m − 1 ) n ans=(2^m-1)^n ans=(2m−1)n.
const int MOD = 1e9 + 7;
void solve() {
int n, m; cin >> n >> m;
cout << qpow(qpow(2, m, MOD) - 1 + MOD, n, MOD);
}
int main() {
solve();
}
原题指路:https://codeforces.com/problemset/problem/1284/B
定义一个序列 a 1 , ⋯ , a l a_1,\cdots,a_l a1,⋯,al是好的,如果存在一对下标 i , j s . t . 1 ≤ i < j ≤ l i,j\ s.t.\ 1\leq i<j\leq l i,j s.t. 1≤i<j≤l,且 a i < a j a_i<a_j ai<aj.定义序列 p p p与 q q q的连接为将 q q q接在 p p p之后,记作 p + q p+q p+q.
给定 n n n个序列 s 1 , ⋯ , s n s_1,\cdots,s_n s1,⋯,sn,求所有的 n 2 n^2 n2对 s x , s y ( 1 ≤ x , y ≤ n ) s_x,s_y\ \ (1\leq x,y\leq n) sx,sy (1≤x,y≤n)中 s . t . s x + s y \ s.t.\ s_x+s_y s.t. sx+sy是好的序列的个数.
第一行输入一个整数 n ( 1 ≤ n ≤ 1 e 5 ) n\ \ (1\leq n\leq 1\mathrm{e}5) n (1≤n≤1e5).接下来 n n n行的第 i ( 1 ≤ i ≤ n ) i\ \ \ (1\leq i\leq n) i (1≤i≤n)行先输入一个整数 l i ( l i > 1 ) l_i\ \ (l_i>1) li (li>1),表示序列 s i s_i si的长度.接下来输入 l i l_i li个整数 s i 1 , s i 2 , ⋯ , s i l ( 0 ≤ s i j ≤ 1 e 6 ) s_{i1},s_{i2},\cdots,s_{il}\ \ (0\leq s_{ij}\leq 1\mathrm{e}6) si1,si2,⋯,sil (0≤sij≤1e6).数据保证 ∑ i = 1 n l i ≤ 1 e 5 \displaystyle \sum_{i=1}^n l_i\leq 1\mathrm{e}5 i=1∑nli≤1e5.
显然一个序列不是好的当且仅当它是一个非升序的序列.设非升序的序列的拼接有 c c c对,则 a n s = n 2 − c ans=n^2-c ans=n2−c.
下面求 c c c:
①若一个序列不是非升序的序列,则它与任一序列拼接后仍不是一个非升序的序列.
②若两个序列 s , t s,t s,t都是非升序的序列且 s + t s+t s+t是非升序的序列的充要条件是: s s s的最后一个元素 ≥ t \geq t ≥t的第一个元素.
m a x n u m i , m i n n u m i maxnum_i,minnum_i maxnumi,minnumi分别表示第 i i i个序列的最大、最小元素,则只需统计 s . t . m i n n u m i ≥ m a x n u m j \ s.t.\ minnum_i\geq maxnum_j s.t. minnumi≥maxnumj的数对 ( i , j ) ( 1 ≤ i , j ≤ n ) (i,j)\ \ (1\leq i,j\leq n) (i,j) (1≤i,j≤n)的个数,这可将 m a x n u m [ ] maxnum[] maxnum[]升序排列后用二分实现.总时间复杂度 O ( ( ∑ i = 1 n l i ) log ( ∑ i = 1 n l i ) ) \displaystyle O\left(\left(\sum_{i=1}^n l_i\right)\log \left(\sum_{i=1}^n l_i\right)\right) O((i=1∑nli)log(i=1∑nli)).
const int MAXN = 1e5 + 5;
int cnt; // 非升序序列的个数
int maxnum[MAXN], minnum[MAXN]; // 非升序序列的最后一个元素、第一个元素
void solve() {
int n; cin >> n;
for (int i = 0; i < n; i++) {
int l; cin >> l;
bool flag = true; // 记录当前序列是否是非升序的序列
maxnum[cnt] = -INF, minnum[cnt] = INF; // 初始化
while (l--) {
int s; cin >> s;
maxnum[cnt] = max(maxnum[cnt], s), minnum[cnt] = min(minnum[cnt], s);
if (s > minnum[cnt]) flag = false; // 不是非升序的序列
}
if (flag) cnt++; // 记录非升序序列的答案
}
sort(maxnum, maxnum + cnt);
ll ans = 0;
for (int i = 0; i < cnt; i++)
ans += upper_bound(maxnum, maxnum + cnt, minnum[i]) - maxnum;
cout << (ll)n * n - ans;
}
int main() {
solve();
}
原题指路:https://codeforces.com/problemset/problem/1284/C
对一个排列 p 1 , ⋯ , p n p_1,\cdots,p_n p1,⋯,pn,定义区间 [ l , r ] [l,r] [l,r]是好的,如果 max { p l , ⋯ , p r } − min { p l , ⋯ , p r } = r − l \max\{p_l,\cdots,p_r\}-\min\{p_l,\cdots,p_r\}=r-l max{pl,⋯,pr}−min{pl,⋯,pr}=r−l.注意对 ∀ i ∈ [ 1 , n ] \forall i\in[1,n] ∀i∈[1,n],区间 [ i , i ] [i,i] [i,i]都是好的.定义一个排列 p 1 , ⋯ , p n p_1,\cdots,p_n p1,⋯,pn的权值为其中好的区间的个数.给定一个整数 n ( 1 ≤ n ≤ 2.5 e 5 ) n\ \ (1\leq n\leq 2.5\mathrm{e}5) n (1≤n≤2.5e5)和一个素数 m ( 1 e 8 ≤ m ≤ 1 e 9 ) m\ \ (1\mathrm{e}8\leq m\leq 1\mathrm{e}9) m (1e8≤m≤1e9),求所有 1 ∼ n 1\sim n 1∼n的排列的权值之和,答案对 m m m取模.
显然若区间 [ l , r ] [l,r] [l,r]是好的,则其中的数是连续的.
考察长度为 i i i的好的区间的个数.从 1 ∼ n 1\sim n 1∼n中选连续的 i i i个数作为区间元素,有 ( n − i + 1 ) (n-i+1) (n−i+1)种情况.区间中的个数可任意排列,有 i ! i! i!种情况.长度为 i i i的区间可排在 1 ∼ n 1\sim n 1∼n个任意位置,且顺序任意,有 A n − i + 1 n − i + 1 = ( n − i + 1 ) ! A_{n-i+1}^{n-i+1}=(n-i+1)! An−i+1n−i+1=(n−i+1)!种情况.故 a n s = ∑ i = 1 n ( n − i + 1 ) ⋅ i ! ⋅ ( n − i + 1 ) ! \displaystyle ans=\sum_{i=1}^n (n-i+1)\cdot i!\cdot (n-i+1)! ans=i=1∑n(n−i+1)⋅i!⋅(n−i+1)!.
const int MAXN = 2.5e5 + 5;
int MOD;
int n;
int fac[MAXN];
void init() {
fac[0] = 1;
for (int i = 1; i < MAXN; i++) fac[i] = (ll)fac[i - 1] * i % MOD;
}
void solve() {
cin >> n >> MOD;
init();
int ans = 0;
for (int i = 1; i <= n; i++) {
int tmp = (ll)(n - i + 1) * fac[i] % MOD * fac[n - i + 1] % MOD;
ans = (ans + tmp) % MOD;
}
cout << ans;
}
int main() {
solve();
}
原题指路:https://codeforces.com/problemset/problem/1288/C
给定两整数 n , m ( 1 ≤ n ≤ 1000 , 1 ≤ m ≤ 10 ) n,m\ \ (1\leq n\leq 1000,1\leq m\leq 10) n,m (1≤n≤1000,1≤m≤10),求满足下列条件的序列对 ( a , b ) (a,b) (a,b)的个数,答案对 1 e 9 + 7 1\mathrm{e}9+7 1e9+7取模:①两序列的长度都为 m m m;②两序列的元素范围为 [ 1 , n ] [1,n] [1,n];③ a i ≤ b i ( 1 ≤ i ≤ m ) a_i\leq b_i\ \ (1\leq i\leq m) ai≤bi (1≤i≤m);④ a [ ] a[] a[]非降序排列;⑤ b [ ] b[] b[]非升序排列.
对条件④和⑤,注意到 a 1 ≤ ⋯ ≤ a m ≤ b m ≤ ⋯ ≤ b 1 a_1\leq \cdots\leq a_m\leq b_m\leq \cdots\leq b_1 a1≤⋯≤am≤bm≤⋯≤b1,即只需考察非降序序列 a [ ] a[] a[]和 b [ ] b[] b[]后考虑 b [ ] b[] b[]的倒序即可.问题转化为求长度为 2 m 2m 2m的、值域为 [ 1 , n ] [1,n] [1,n]的非降序序列的个数.
设值为 i i i的数的个数为 x i x_i xi,则 x 1 + ⋯ + x n = 2 m x_1+\cdots+x_n=2m x1+⋯+xn=2m,问题转化为求该不定方程的非负整数解的个数,即 C n + 2 m − 1 n − 1 C_{n+2m-1}^{n-1} Cn+2m−1n−1.
const int MAXN = 2005;
const int MOD = 1e9 + 7;
int fac[MAXN], ifac[MAXN];
void init() { // 预处理阶乘及其逆元
fac[0] = 1;
for (int i = 1; i < MAXN; i++) fac[i] = (ll)fac[i - 1] * i % MOD;
ifac[MAXN - 1] = qpow(fac[MAXN - 1], MOD - 2, MOD);
for (int i = MAXN - 1; i; i--) ifac[i - 1] = (ll)ifac[i] * i % MOD;
}
int C(int n, int m) {
return (ll)fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}
void solve() {
init();
int n, m; cin >> n >> m;
cout << C(n + 2 * m - 1, n - 1);
}
int main() {
solve();
}
a [ i ] [ j ] a[i][j] a[i][j]表示长度为 i i i的、以 j j j结尾的非降序序列的个数, b [ i ] [ j ] b[i][j] b[i][j]表示长度为 i i i的、以 j j j结尾的非升序序列的个数.以 a [ ] [ ] a[][] a[][]为例,状态转移方程 a [ i ] [ j ] = ∑ k = 1 j a [ i − 1 ] [ k ] \displaystyle a[i][j]=\sum_{k=1}^j a[i-1][k] a[i][j]=k=1∑ja[i−1][k].最终答案 a n s = ∑ i = 1 n ∑ j = i n a [ m ] [ i ] ⋅ b [ m ] [ j ] \displaystyle ans=\sum_{i=1}^n \sum_{j=i}^n a[m][i]\cdot b[m][j] ans=i=1∑nj=i∑na[m][i]⋅b[m][j],初始条件 a [ 1 ] [ i ] = b [ 1 ] [ i ] = 1 ( 1 ≤ i ≤ n ) a[1][i]=b[1][i]=1\ \ (1\leq i\leq n) a[1][i]=b[1][i]=1 (1≤i≤n).总时间复杂度 O ( n 2 m ) O(n^2m) O(n2m).
const int MAXN = 2005;
const int MOD = 1e9 + 7;
int a[MAXN][MAXN]; // a[i][j]表示长度为i的、以j结尾的非降序序列的个数
int b[MAXN][MAXN]; // b[i][j]表示长度为i的、以j结尾的非升序序列的个数
void solve() {
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i++) a[1][i] = b[1][i] = 1; // 初始条件
for (int i = 2; i <= m; i++) { // 枚举长度
for (int j = 1; j <= n; j++) { // 枚举结尾数
for (int k = 1; k <= j; k++) // 枚举倒数第二个数
a[i][j] = (a[i][j] + a[i - 1][k]) % MOD;
}
}
for (int i = 2; i <= m; i++) { // 枚举长度
for (int j = 1; j <= n; j++) { // 枚举结尾数
for (int k = j; k <= n; k++) // 枚举倒数第二个数
b[i][j] = (b[i][j] + b[i - 1][k]) % MOD;
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++)
ans = ((ll)ans + (ll)a[m][i] * b[m][j]) % MOD;
}
cout << ans;
}
int main() {
solve();
}
a [ i ] [ j ] a[i][j] a[i][j]表示长度为 i i i的、以 j j j结尾的非降序序列的个数, b [ i ] [ j ] b[i][j] b[i][j]表示长度为 i i i的、以 j j j结尾的非升序序列的个数.由隔板法: a [ m ] [ i ] = C m + i − 2 m − 1 , b [ m ] [ i ] = C m + n − i − 1 m − 1 a[m][i]=C_{m+i-2}^{m-1},b[m][i]=C_{m+n-i-1}^{m-1} a[m][i]=Cm+i−2m−1,b[m][i]=Cm+n−i−1m−1,则 a n s = ∑ i = 1 n ∑ j = 1 i C m + j − 2 m − 1 ⋅ C m + n − i − 1 m − 1 \displaystyle ans=\sum_{i=1}^n \sum_{j=1}^i C_{m+j-2}^{m-1}\cdot C_{m+n-i-1}^{m-1} ans=i=1∑nj=1∑iCm+j−2m−1⋅Cm+n−i−1m−1.
预处理出 C m + j − 2 m − 1 C_{m+j-2}^{m-1} Cm+j−2m−1的前缀和 p r e i = ∑ j = 1 i C m + j − 2 m − 1 \displaystyle pre_i=\sum_{j=1}^i C_{m+j-2}^{m-1} prei=j=1∑iCm+j−2m−1,则 a n s = ∑ i = 1 n C m + n − i − 1 m − 1 ⋅ p r e i \displaystyle ans=\sum_{i=1}^n C_{m+n-i-1}^{m-1}\cdot pre_i ans=i=1∑nCm+n−i−1m−1⋅prei,总时间复杂度 O ( n + m ) O(n+m) O(n+m).
const int MAXN = 2005;
const int MOD = 1e9 + 7;
int fac[MAXN], ifac[MAXN];
int pre[MAXN]; // pre[i]=Σ_{j=1}^{i} C(m+j-2,m-1)
void init() { // 预处理阶乘及其逆元
fac[0] = 1;
for (int i = 1; i < MAXN; i++) fac[i] = (ll)fac[i - 1] * i % MOD;
ifac[MAXN - 1] = qpow(fac[MAXN - 1], MOD - 2, MOD);
for (int i = MAXN - 1; i; i--) ifac[i - 1] = (ll)ifac[i] * i % MOD;
}
int C(int n, int m) {
return (ll)fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}
void solve() {
init();
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i++) pre[i] = ((ll)pre[i - 1] + C(m + i - 2, m - 1)) % MOD;
int ans = 0;
for (int i = 1; i <= n; i++) ans = ((ll)ans + (ll)pre[i] * C(m + n - i - 1, m - 1)) % MOD;
cout << ans;
}
int main() {
solve();
}
d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k]表示长度为 i i i的、 a [ ] a[] a[]以 j j j结尾、 b [ ] b[] b[]以 k k k结尾的序列的个数,则 a n s = ∑ i = 1 m ∑ j = 1 n ∑ k = 1 n d p [ i ] [ j ] [ k ] \displaystyle ans=\sum_{i=1}^m \sum_{j=1}^n \sum_{k=1}^n dp[i][j][k] ans=i=1∑mj=1∑nk=1∑ndp[i][j][k].初始条件 d p [ 1 ] [ j ] [ k ] = [ k ≥ j ] dp[1][j][k]=[k\geq j] dp[1][j][k]=[k≥j].
状态转移方程 d p [ i ] [ j ] [ k ] = ∑ p = 1 j ∑ q = k n d p [ i − 1 ] [ p ] [ q ] \displaystyle dp[i][j][k]=\sum_{p=1}^j \sum_{q=k}^n dp[i-1][p][q] dp[i][j][k]=p=1∑jq=k∑ndp[i−1][p][q],直接计算会TLE,显然可用二维前缀和优化,时间复杂度 O ( n 2 m ) O(n^2m) O(n2m).注意数组开不了那么大,要用滚动数组.
const int MAXN = 2005;
const int MOD = 1e9 + 7;
int fac[MAXN], ifac[MAXN];
int dp[2][MAXN][MAXN]; // dp[i][j][k]表示长度为i的、a[]以j结尾、b[]以k结尾的序列的个数
int pre[2][MAXN][MAXN]; // dp[][][]的二维前缀和
void solve() {
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i++) // 初始条件
for (int j = i; j <= n; j++) dp[1][i][j] = 1;
for (int i = 1; i <= n; i++) { // 求dp[1][][]的二维前缀和
for (int j = 1; j <= n; j++)
pre[1][i][j] = pre[1][i - 1][j] + pre[1][i][j - 1] - pre[1][i - 1][j - 1] + dp[1][i][j];
}
for (int i = 2; i <= m; i++) {
for (int j = 1; j <= n; j++) {
for (int k = j; k <= n; k++) {
dp[i & 1][j][k] = ((ll)pre[(i - 1) & 1][j][n] - pre[(i - 1) & 1][j][k - 1]
- pre[(i - 1) & 1][0][n] + pre[(i - 1) & 1][0][k - 1]) % MOD;
}
}
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
pre[i & 1][j][k] = ((ll)pre[i & 1][j - 1][k] + pre[i & 1][j][k - 1]
- pre[i & 1][j - 1][k - 1] + dp[i & 1][j][k]) % MOD;
}
}
}
cout << (pre[m & 1][n][n] % MOD + MOD) % MOD;
}
int main() {
solve();
}
原题指路:https://codeforces.com/problemset/problem/1305/C
给定一个长度为 n ( 2 ≤ n ≤ 2 e 5 ) n\ \ (2\leq n\leq 2\mathrm{e}5) n (2≤n≤2e5)的序列 a 1 , ⋯ , a n ( 0 ≤ a i ≤ 1 e 9 ) a_1,\cdots,a_n\ \ (0\leq a_i\leq 1\mathrm{e}9) a1,⋯,an (0≤ai≤1e9)和一个整数 m ( 1 ≤ m ≤ 1000 ) m\ \ (1\leq m\leq 1000) m (1≤m≤1000),求 ∏ 1 ≤ i < j ≤ n ∣ a i − a j ∣ \displaystyle \prod_{1\leq i<j\leq n}|a_i-a_j| 1≤i<j≤n∏∣ai−aj∣,答案对 m m m取模.
① n ≤ m n\leq m n≤m时,暴力求即可.
② n > m n>m n>m时,因模 m m m只有 m m m种余数,则至少存在两个数 a i , a j s . t . a i ≡ a j ( m o d m ) a_i,a_j\ s.t.\ a_i\equiv a_j\ \ (\mathrm{mod}\ m) ai,aj s.t. ai≡aj (mod m),故 a n s = 0 ans=0 ans=0.
void solve() {
int n, m; cin >> n >> m;
vi a(n);
for (auto& ai : a) cin >> ai;
if (n > m) cout << 0;
else {
int ans = 1;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) ans = (ll)abs(a[i] - a[j]) % m * ans % m;
cout << ans;
}
}
int main() {
solve();
}