Atcoder abc315

發表於 更新於 分類於 ， Disqus： 文章字數： 1.4k 所需閱讀時間 ≈ 5 分鐘
G(exgcd)Ex(分治卷积)

https://atcoder.jp/contests/abc315

G - Ai + Bj + Ck = X (1 <= i, j, k <= N)

给定a,b,c,x,n 找满足限制的方案数

n 1e6

a,b,c [1,1e9]

x 3e15

2s

1024mb

我的思路

显然 for i = 1..n, 剩余部分exgcd算一算

但是wa了17个点，感觉我的exgcd应该是overflow了

题解

和我过程一模一样但是没有代码, 会overflow的代码,(不过本身逻辑没问题用python可能就过了)

1
2
3
4
5
6
7
8
9
// ax+by=c, gcd(a,b)=1, return {x,y}
tuple<ll,ll> exgcd(ll a,ll b,ll c){
  if(b == 0) {
    assert(a==1);
    return {c, 0};
  }
  auto [_x,_y] = exgcd(b,a%b, c);
  return {_y,_x - (a/b) * _y}; // overflow????
}

修复后的代码

1
2
3
4
5
6
// ax+by=gcd(a,b), 不传入c，返回{x,y,gcd(a,b)}
tuple<ll,ll,ll> exgcd(ll a,ll b){
  if(b == 0) return {1,0,a};
  auto [_x,_y,g] = exgcd(b,a%b);
  return {_y,_x - (a/b) * _y, g};
}

代码

https://atcoder.jp/contests/abc315/submissions/me

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
ll read(){ll r;scanf("%lld",&r);return r;}
// ax+by=gcd(a,b), return {x,y,gcd(a,b)}
// ((a/b)*b+a%b) x + by = gcd(a,b)
// b (y+(a/b)x) + (a%b) x = gcd(a,b)
tuple<ll,ll,ll> exgcd(ll a,ll b){
  if(b == 0) return {1,0,a};
  auto [_x,_y,g] = exgcd(b,a%b);
  return {_y,_x - (a/b) * _y, g};
}

ll mod(ll a,ll b){return (a%b+b)%b;} // [0,b)
ll floordiv(ll a,ll b){ return (a-mod(a,b))/b; } // a = kb + [0,b) return k
ll ceildiv(ll a,ll b){ return (a-mod(a,b))/b + !!(mod(a,b)); } // a = kb + (-b,0] return k
ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b); }
// count( (x,y) \in[1,n]) ,  ax+by=c
ll solve(ll a,ll b,ll c,ll n){
  if(c <= 0) return 0;
  auto [x,y,g] = exgcd(a,b); // gcd(a,b) = 1
  if(c % g != 0) return 0;
  a/=g; b/=g; c/=g;
  assert(a*x+b*y==1); // c*x*a+c*b*y==c
  // ax+by=1 => =c
  // find min(x > 0)
  // 每次 x-=b,y+=a 结果不变
  // cax+byc=c
  // 找最小正数 = cx % b
  x = ((c%b)*(x%b)%b+(b-1))%b+1; // (0,b]
  if(a*x > c) return 0;
  y = (c-a*x)/b;
  assert(a*x+b*y==c);
  // (x+kb,y-ka)
  // 1<= x+kb <= n
  // 1<= y-ka <= n
  int maxk = min(floordiv(n-x,b), floordiv(y-1,a));
  int mink = max(ceildiv(1-x,b), ceildiv(y-n,a));
  return mink<=maxk?maxk-mink+1:0;
}

int main(){
  // ai + bj + ck = x count( (i,j,k) \in [1,n])
  ll n = read(); // 1e6
  ll a = read(); // [1,1e9]
  ll b = read(); // [1,1e9]
  ll c = read(); // [1,1e9]
  ll x = read(); // [1,3e15]
  ll m = gcd(gcd(a,b),gcd(c,x));
  a/=m; b/=m; c/=m; x/=m;
  ll ans = 0;
  rep(i,1,n+1) ans += solve(b,c,x-a*i,n);
  printf("%lld\n",ans);
  return 0;
}
// 非常质朴的一道题
// 很有gcd/exgcd的想法
// a,b,c,x
// 就暴力for i,然后exgcd没了??

Ex - Typical Convolution Problem

$a_{1\cdots n} \in [1,2\cdot 10^5]$

$f_0 = 1$
$f_k = a_k \cdot (\sum_{i+j<k} f_i\cdot f_j)$

求所有 $f_{1\cdots n}\mod 998244353$

5s

1024mb

我的思路

令 $G_k = \sum_{i+j=k} F_iF_j$

$G = F\star F$

$F_k=A_k(\sum_{i<k} G_i)$

似乎就是个二分过程中做卷积? 以前abc做过的

ac了

代码

https://atcoder.jp/contests/abc315/submissions/49604273

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
#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/convolution>
const int MOD=998244353; // 2^23 = 8388608, (MOD-1)%(2^23) == 0
using mint = atcoder::static_modint<MOD>;
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
#define per(i,a,n) for (ll i=n;i-->(ll)(a);)
ll read(){ll r;scanf("%lld",&r);return r;}
vector<mint> a(400010,0);
vector<mint> f(400010,0);
vector<mint> f2(400010,0); // f2 = f*f
vector<mint> pf2(400010,0); // pf2[i] = pf2[i-1] + f2[i] , prefixsum
// 递归+二分+卷积
// 每次完成 [l,r) 的f计算和f2计算
// f2[i] = sum f[j]*f[i-j] = f*f
// f[i] = a[i] * sum f2[<i] = ai * pf2[i]
// 计算[l,r)
//    - 且 [0,l) 之前已经计算好
//    - 且 [0,l) 内部卷积 对当前区间的贡献之前已经计算好
void calc(int l,int r){ // 保证长度是2的幂次, r-n = 2^k
  if(l+1==r){
    if(l == 0) return ;
    f[l] = a[l] * pf2[l-1];
    f2[l] += f[l]*f[0]*2;
    pf2[l] = pf2[l-1] + f2[l];
    return ;
  }
  int mid=(l+r)/2;
  int sz = r-l;
  assert((sz&(sz-1) ) ==0); // 长度是2的倍数
  calc(l,mid);
  // 计算 [l,mid) 对 [mid,r)的贡献
  vector<mint> l2mid = {};
  rep(i,l,mid) l2mid.push_back(f[i]);
  vector<mint> prefix= {};
  if(l == 0){
    rep(i,0,mid) prefix.push_back(f[i]);
    auto c = atcoder::convolution(l2mid,prefix); //convolution([0...],[l...])
    rep(i,mid,r) f2[i] += c[i-l];
  }else{
    rep(i,0,r-l) prefix.push_back(f[i]);
    auto c = atcoder::convolution(l2mid,prefix); //convolution([0...],[l...])
    rep(i,mid,r) f2[i] += 2*c[i-l]; // 平方！对称2次贡献
  }
  calc(mid,r);
}

int main(){
  int n=read();
  rep(i,1,n+1) a[i]=read();
  pf2[0] = f2[0] = f[0] = 1;
  int nn=n*2;
  while((nn & (nn+1)) != 0 ) nn = (nn&(nn+1))-1; // 长度 [0,nn] 是二的倍数
  calc(0,nn+1);
  rep(i,1,n+1) printf("%d ",f[i].val());
  return 0;
}

参考

https://atcoder.jp/contests/abc315/editorial

总结

第一次真的overflow了，我去官方的dropbox下载了数据，真的是overflow, 总的来说还是需要一个正确的不会overflow的

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
oi test -i in/test_69.txt -o out/test_69.txt  
[('/home/cromarmot/Documents/computer/oiCode/dist/AtCoder/abc315/G/in/test_69.txt', '/home/cromarmot/Documents/compu  
ter/oiCode/dist/AtCoder/abc315/G/out/test_69.txt')]  
  
[INFO]: Tester folder: /home/cromarmot/Documents/computer/oiCode/dist/AtCoder/abc315/G/TEST  
[INFO]: Start compiling.  
[INFO]: Run [clang++ -o Main Main.cpp -std=gnu++17 -O2 -g -Wall -Wcomma -Wextra -fsanitize=integer,undefined,null,al  
ignment]  
[INFO]: Successful compilation.  
[INFO]: Execute: [['./Main']]  
stderr: Main.cpp:15:25: runtime error: signed integer overflow: 13 * -790827376684848793 cannot be represented in ty  
pe 'long long'  
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior Main.cpp:15:25 in    
Main.cpp:15:17: runtime error: signed integer overflow: -7402556864166049505 - 6611729487481200712 cannot be represe  
nted in type 'long long'  
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior Main.cpp:15:17 in    
Main.cpp:29:3: runtime error: signed integer overflow: 701151656 * 3588519056455479667 cannot be represented in type  
'long long'  
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior Main.cpp:29:3 in    
Main.cpp:29:3: runtime error: signed integer overflow: 947037805 * 7318597677910819784 cannot be represented in type  
'long long'  
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior Main.cpp:29:3 in    
Main.cpp:29:3: runtime error: signed integer overflow: -9223335515789506216 + -9223341652767361684 cannot be represe  
nted in type 'long long'  
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior Main.cpp:29:3 in    
  
TestCase            test_69.txt => test_69.txt  
Time spend          0.703432 s                   
Virtual Memory      18.04 MB                     
Files /home/cromarmot/Documents/computer/oiCode/dist/AtCoder/abc315/G/out/test_69.txt and /home/cromarmot/Documents/  
computer/oiCode/dist/AtCoder/abc315/G/TEST/test_69.txt differ  
  
==============================================================================                                         
1000000 165613875 701151656 947037805 85081109851091                                                                   
                                                                                                                      
-  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  - -                                         
34                                                            | 0                                                      
                                                                                                                      
==============================================================================

Ex 在补完了之前的abc的情况下不难