https://atcoder.jp/contests/abc276/tasks
G - Count Sequences
范围 [0,m] 单调递增 n个数, 且相邻 mod 3 不同
问 方案数 mod 998244353
范围
n 1e7
m 1e7
4s
1024mb
我的思路
f(n,m) = 范围 [0,m] 放n个数, 第一个放0 的方案数
ans = sum f(n,0..m)
f(n,m) = sum f(n-1,m-非3倍数)
考虑 生成函数 f(n,m) 为 生成函数$F_n$的系数
$F_1 = 1+x+x^2+x^3+\cdots = \frac{1}{1-x}$
$ans = \lbrack x^m \rbrack (F_n \cdot \frac{1}{1-x}) $
$F_i = F_{i-1} \cdot (x+x^2+x^4+x^5+x^7+x^8+\cdots)$
$= F_{i-1} \cdot \frac{x+x^2}{1-x^3}$
$F_n = F_1 \cdot (\frac{x+x^2}{1-x^3})^{n-1} $
$ans = \lbrack x^m \rbrack \frac{(x+x^2)^{n-1}}{(1-x)^2(1-x^3)^{n-1}}$
然后 我暴力算 样例就TLE了
题解
令 b1=a1, 其它的为相邻ai的差, 那么和 <= m, b[2..]是mod 3非0的数
每个bi考虑把它分成两部分
3的倍数的部分 y 和 mod3 的部分x
x的部分就是 第一个 0,1,2, 后面的1,2
sum y <= (m - sum x)/3
y 就是小球插球法, 可以均摊O(1),
(n个非负数 和小于等于s, 不妨设s-这些数的和为最后一个数, 就是n+1个非负数和为s, n+1个正数 和为s+n+1, s+n个空隙插入n个板子 binom(s+n,n)
然后 x的和 的出现次数 可以类似排列组合就没了
和为s
0 + n-1个(1,2) = [n-1..2(n-1)] = binom(n-1,s-(n-1))
1 + n-1个(1,2) = [n..2(n-1)+1] = binom(n-1,s-1-(n-1))
2 + n-1个(1,2) = [n+1..2(n-1)+2] = binom(n-1,s-2-(n-1))
代码
https://atcoder.jp/contests/abc276/submissions/36273738
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/convolution>
const int MOD = 998244353;
using mint = atcoder::static_modint<MOD>;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)
int read(){int r;scanf("%d",&r);return r;}
const int N=14000000;
mint fac[N+10]={1};
mint ifac[N+10];
mint binom(int n,int m){return (m>n||m<0)?0:(fac[n]*ifac[m]*ifac[n-m]);}
int main(){
rep(i,1,N+1) fac[i]=fac[i-1]*i;
ifac[N]=fac[N].inv();
per(i,0,N) ifac[i]=ifac[i+1]*(i+1);
int n=read();
int m=read();
mint ans =0;
rep(s12,0,m+1){
mint s=0;
rep(fi,0,3) s+=binom(n-1,s12-fi-(n-1));
ans += s*binom(n+(m-s12)/3,n);
}
printf("%d\n",ans.val());
return 0;
}
|
Ex - Construct a Matrix
构造一个n * n的0/1/2矩阵
满足q个限制, 在子矩阵[ai..bi]x[ci..di] 中所有数的乘积 mod 3 == ei
限制
n, q 2000
4s
1024mb
我的思路
乘积转换一下
ei = 0 就是 子矩阵中至少存在一个0
ei = 1 就是 子矩阵中不存在0, 且2的出现次数是偶数次
ei = 2 就是 子矩阵中不存在0, 且2的出现次数是奇数次
0的部分很好处理, 把ei=1,2的全部标注, 只要是否含有查询未被标注 合法就行, 未被标注的全部填0.
问题是1和2的部分, 给多个框, 要一些框里奇数个1,一些框里偶数个1
题解
0的部分一样
1和2的部分等于在(0,1)的值域内 的 Q个等式的 线性方程
但是对于n^2个未知数, q个方程直接高斯消元速度并不够
需要二维前缀和的想法,让每个不等式左侧只有4个数,这样就是 4q个未知数, q个方程了, 然后再上个bitset 随便搞
然后要注意的是, 这里转换成 4个二维前缀xor和以后, 这些位置 可能是填0的,
1
2
3
4
5
6
7
8
9
10
| 21
10
1
x
x 需要奇数2
xx 需要奇数2
x 需要奇数2
|
这样解矩阵可能会是
这样会炸掉?
一个我感觉自己绕了很久的东西终于想通了
也就是 当变成4个前缀xor时, 有的位置并没有被1,2 覆盖
而这些位置可能正好需要填写零, 那么如果一个方案中填写2了, 再去用0覆盖就会影响2的个数
实际上并不是, 问题在于, 要求的是前缀和的地方 会是填0的地方, 但是通过前缀和还原成原数组的话, 虽然依然可能在需要填0的地方填2, 但还原以后, 不被覆盖的位置就再也不会影响1和2的计数了,
代码
https://atcoder.jp/contests/abc276/submissions/36294660
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
| #include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)
int read(){int r;scanf("%d",&r);return r;}
const int N=2000;
int main(){
int n=read();
int q=read();
vector<array<int,5>>Q;
rep(i,0,q) Q.push_back({read(),read(),read(),read(),read()});
vector<pair<int,int> > idx;
for(auto [a,b,c,d,e]:Q)if(e) for(auto i:{a-1,b})for(auto j:{c-1,d}) if(i>0&&j>0) idx.push_back({i,j});
sort(begin(idx),end(idx));
idx.resize(unique(begin(idx),end(idx))-begin(idx));
auto lb=[&](int i,int j){return lower_bound(begin(idx),end(idx),make_pair(i,j))-begin(idx);};
vector<bitset<4*N+1>> matrix = {};
for(auto [a,b,c,d,e]:Q)if(e){
bitset<4*N+1>row;
for(auto i:{a-1,b})for(auto j:{c-1,d})if(i>0&&j>0) row[lb(i,j)]=1;
row[4*N]=(e==2);
matrix.push_back(row);
}
vector<bool>v12(idx.size());
{
int i=0;
rep(j,0,4*N+1){
if(i>=(int)matrix.size())break;
rep(ii,i,matrix.size()) if(matrix[ii][j]){
swap(matrix[i],matrix[ii]);
break;
}
if(!matrix[i][j])continue;
if(j==4*N){
printf("No\n");
return {};
}
rep(k,0,matrix.size())if(k!=i && matrix[k][j]) matrix[k]^=matrix[i];
i++;
}
}
auto ans=vector(n+1,vector(n+1,0));
rep(i,0,matrix.size()){
rep(j,0,4*N+1)if(matrix[i][j]){
auto [pi,pj]=idx[j];
ans[pi][pj]=matrix[i][4*N];
break;
}
}
per(i,1,n+1)rep(j,1,n+1) ans[i][j]^=ans[i-1][j];
rep(i,1,n+1)per(j,1,n+1) ans[i][j]^=ans[i][j-1];
auto inc = vector(n+2,vector<array<int,3>>());
auto pre = vector(n+2,0);
for(auto [a,b,c,d,e]:Q)if(e){
inc[a].push_back({c,d,1});
inc[b+1].push_back({c,d,-1});
}
rep(i,1,n+1){
for(auto [c,d,diff]:inc[i]){
pre[c]+=diff;
pre[d+1]-=diff;
}
int v=0;
rep(j,1,n+1){
v+=pre[j];
if(v) ans[i][j]++;
else ans[i][j]=0;
}
}
auto ans0=ans;
rep(i,1,n+1)rep(j,1,n+1)ans0[i][j]=(ans[i][j]==0)+ans0[i-1][j]+ans0[i][j-1]-ans0[i-1][j-1];
for(auto [a,b,c,d,e]:Q)if(!e)if(ans0[b][d]-ans0[a-1][d]-ans0[b][c-1]+ans0[a-1][c-1] == 0){
printf("No\n");
return 0;
}
printf("Yes\n");
rep(i,1,ans.size())rep(j,1,ans.size()) printf("%d%c",ans[i][j]," \n"[j+1==(int)ans.size()]);
return 0;
}
|
总结
G
不会数数…哎
其实1e7基本注定了连 n log n都是不行的, 要么就是 O(n) 要么就是数学怎么搞一搞 O(1)或者O(log n)
TODO 广义二项式定理
Ex
二位数组前缀和 用了无数次也写了无数次了, 但是倒过来竟然就想不到了,哎
然后这个0 在最后还是卡了我逻辑, 看了snuke的代码, 又想了想才想通, 并不会冲突
另外也是 和一维前缀同理 1…n = pre[n]-pre[0], 虽然pre[0]在实际上只能=0,但是运算中就是可以让它不为0,还原后的结果只要是对的,就是期望的!, 所以snuke 处理的时候 始终都是4个的 容斥和!
参考
官方题解