Starry

发表于 更新于 分类于 本文字数： 367 阅读时长 ≈ 1 分钟

NTT那块还要再看一下。。。

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
#include <cstdio>
#include <iostream>
#include <cmath>

typedef long long ll;
const int NR = 1 << 22, g = 3, gi = 332748118, mod = 998244353;

using namespace std;
int n, m, rev[NR];
ll a[NR], b[NR],c[NR],d[NR];
ll quikpow(ll a, ll k)
{
    ll res = 1;
    while (k > 0)
    {
        if (k&1)res=res*a%mod;
        a=a*a%mod;
        k>>=1;
    }
    return res;
}

void NTT(ll *a,int n,int type){
    for(int i=0;i<=n;++i){
        if(i<rev[i])swap(a[i],a[rev[i]]);
    }
    for(int i=1;i<n;i<<=1){
        ll gn=quikpow(type?g:gi,(mod-1)/(i<<1));
        for(int j=0;j<n;j+=(i<<1)){
            ll g0=1;
            for(int k=0;k<i;++k,g0=g0*gn%mod){
                ll x=a[j+k],y=g0*a[i+j+k]%mod;
                a[j+k]=(x+y)%mod;
                a[i+j+k]=(x-y+mod)%mod;
            }
        }
    }
    if(type==1)return ;
    ll inv =  quikpow(n, mod - 2);
    //reverse(a+1,a+n);
    for(int i=0;i<n;++i)a[i]=a[i]*inv%mod;
}

void cdq(int l,int r){
    if(l==r)return;
    int mid=(l+r)>>1;
    cdq(l,mid);

    int ttt=(r-l+1)<<1,len=1<<max((int)ceil(log2(ttt)),1);
    for(int i=0;i<len;++i){
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(max((int)ceil(log2(ttt)),1)-1));
    }

    for(int i=0;i<len;++i)c[i]=d[i]=0;
    for(int i=l;i<=r;++i)c[i-l]=a[i-l];
    for(int i=l;i<=mid;++i)d[i-l]=b[i];
    NTT(c,len,1);
    NTT(d,len,1);
    for(int i=0;i<len;++i)c[i]=c[i]*d[i]%mod;
    NTT(c,len,0);
    for(int i=mid+1;i<=r;++i)b[i]=(b[i]+c[i-l])%mod;
    cdq(mid+1,r);
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<n;++i)scanf("%lld",a+i);
    b[0]=1;
    cdq(0,n-1);
    
    for(int i=0;i<n;++i)printf("%lld ",b[i]);
    return 0;
}

发表于 更新于 分类于 本文字数： 283 阅读时长 ≈ 1 分钟

NTT的做法

ec好像是linux的机子，回头学下gdb调试 
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
#include <cstdio>
#include <iostream>
#include <cmath>

typedef long long ll;
const int NR = 1 << 22, g = 3, gi = 332748118, mod = 998244353;

using namespace std;
int n, m, rev[NR];
ll a[NR], b[NR];
ll quikpow(ll a, ll k)
{
    ll res = 1;
    while (k > 0)
    {
        if (k&1)res=res*a%mod;
        a=a*a%mod;
        k>>=1;
    }
    return res;
}

void NTT(ll *a,int n,int type){
    for(int i=0;i<=n;++i){
        if(i<rev[i])swap(a[i],a[rev[i]]);
    }
    for(int i=1;i<n;i<<=1){
        ll gn=quikpow(type?g:gi,(mod-1)/(i<<1));
        for(int j=0;j<n;j+=(i<<1)){
            ll g0=1;
            for(int k=0;k<i;++k,g0=g0*gn%mod){
                ll x=a[j+k],y=g0*a[i+j+k]%mod;
                a[j+k]=(x+y)%mod;
                a[i+j+k]=(x-y+mod)%mod;
            }
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;++i)scanf("%lld",a+i);
    for(int i=0;i<=m;++i)scanf("%lld",b+i);
    int len=1<<max((int)ceil(log2(n+m)),1);
    for(int i=0;i<len;++i){
        rev[i]=(rev[i>>1]>>1)|((i&1)<<(max((int)ceil(log2(n+m)),1)-1));
    }

    NTT(a,len,1);
    NTT(b,len,1);
    for(int i=0;i<=len;++i)a[i]=a[i]*b[i]%mod;
    NTT(a,len,0);
    ll inv=quikpow(len,mod-2);
    for(int i=0;i<=n+m;++i)printf("%lld ",a[i]*inv%mod);
    return 0;
}

发表于 更新于 分类于 本文字数： 397 阅读时长 ≈ 1 分钟 
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
87
88
89
90
91
#include<cstdio>
#include<queue>
#include<cstring>

using namespace std;

const int N=125100;
int n,m,s,t,tot=1,hd[(int)6e4],cur[(int)6e4],ss,tt,dep[(int)6e4];
long long flow[(int)6e4],l[N];
struct Edge
{
    int to,nxt;
    long long val;
}e[N*3+99];
inline void add(int u,int v,long long w){
    e[++tot]={v,hd[u],w},hd[u]=tot;
    e[++tot]={u,hd[v],0ll},hd[v]=tot;
}

bool bfs(int st,int en){
    for(int i=0;i<=n+2;++i)dep[i]=0;
    queue<int> q;
    memcpy(cur,hd,sizeof(hd));
    q.push(st);
    dep[st]=1;

    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int eg=hd[u];eg;eg=e[eg].nxt){
            if(!dep[e[eg].to]&&e[eg].val>0){
                dep[e[eg].to]=dep[u]+1;
                q.push(e[eg].to);
            }
        }
    }
    return !!dep[en];
}

long long dfs(int u,int en,long long flow){
    //printf("%d-%d\n",u,en);
    if(u==en)return flow;
    long long r=flow;
    for (int eg = cur[u]; eg && r; eg = e[eg].nxt)
    {
        //printf("%d-(%d---%d)-%d__%lld\n",eg,e[eg].to,u,e[eg].nxt,r);
        cur[u] = eg;
        if (e[eg].val>0 && dep[e[eg].to] == dep[u] + 1)
        {
            long long c = dfs(e[eg].to,en, min(r, e[eg].val));
            //printf("%lld\n",c);
            r -= c;
            e[eg].val -= c;
            e[eg ^ 1].val += c;
        }
    }
    return flow - r;
}

long long Dinic(int st,int en){
    long long ret=0;
    while(bfs(st,en))ret+=dfs(st,en,1ll<<53);
    //printf("%lld__\n",ret);
    return ret;
}

int main(){
    long long tmp,sum=0;
    scanf("%d%d%d%d",&n,&m,&s,&t);
    tt=n+1;
    for(int i=1,w,x;i<=m;++i){
        long long y,z;
        scanf("%d%d%lld%lld",&w,&x,&y,&z);
        l[i]=y;
        add(w,x,z-y);
        flow[w]-=l[i],flow[x]+=l[i];
    }
    for(int i=1;i<=n;++i){
        if(flow[i]>0){
            sum+=flow[i];
            add(ss,i,flow[i]);
        }else if(flow[i]<0)add(i,tt,-flow[i]);
    }
    add(t,s,1ll<<53);
    if(sum==Dinic(ss,tt)){
        tmp=e[tot].val;
        e[tot].val=e[tot^1].val=0;
        printf("%lld\n",tmp - Dinic(t, s));
    }else puts("please go home to sleep");
    return 0;
}

发表于 更新于 本文字数： 28 阅读时长 ≈ 1 分钟

cf predictor引入的jquery墙了，控制台插入：

1
2
3
var script = document.createElement('script');
script.src = "https://lib.baomitu.com/jquery/3.3.1/jquery.min.js";
document.getElementsByTagName('head')[0].appendChild(script);

发表于 更新于 分类于 本文字数： 372 阅读时长 ≈ 1 分钟 
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <algorithm>
#include <bitset>
#include <map>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <cmath>
#include <stack>
#include <set>
#include <queue>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define sqr(x) (x) * (x)
#define pr1(x) printf("Case %d: ", x)
#define pn1(x) printf("Case %d:\n", x)
#define pr2(x) printf("Case #%d: ", x)
#define pn2(x) printf("Case #%d:\n", x)
#define lowbit(x) (x & (-x))

#define fi first
#define se second
#define sz(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

int n, a[100000 + 99], lo[100000 + 9], f[100009][20],cnt;

int gcd(int ma,int mi){
    return mi?gcd(mi,ma%mi):ma;
}

inline int rmq_gcd(int l,int r){
    int k=lo[r-l+1];
    return gcd(f[l][k],f[r-(1<<k)+1][k]);
}

int ck(int l,int r){
    return rmq_gcd(l,r)==1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> a[1];
    f[1][0] = a[1];
    cnt+=a[1]!=1;
    for (int i = 2; i <= n; ++i)
    {
        cin >> a[i];
        cnt+=a[i]!=1;
        f[i][0] = a[i];
        lo[i] = lo[i >> 1] + 1;
    }
    for (int j = 1; j <= 17; ++j)
    {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i)
        {
            f[i][j] = gcd(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }
    if(!ck(1,n)){
        cout<<"-1";
        return 0;
    }
    int ans=0x3f3f3f3f;
    for(int i=1;i<=n;++i){
        if(!ck(i,n))continue;
        int l=i,r=n;
        while(l<r){
            int mid=(l+r)>>1;
            if(ck(i,mid))r=mid;
            else l=mid+1;
        }
        if(r==i)ans=min(ans,cnt);
        else ans=min(ans,r-i+cnt-1);
    }
    cout<<ans;
    return 0;
}
0%