Starry

发表于 更新于 分类于 本文字数： 563 阅读时长 ≈ 2 分钟 
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
102
103
104
105
106
107
108
109
110
111
112
#include <bits/stdc++.h>
/*
#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 scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#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;

using ll=long long;
const int mod=786433,NR=1<<18,g=10,gi=235930;
//const int mod=998244353,g=3,gi=332748118,NR=1<<21;

int powmod(int a,int b){
	int res=1;
	for(;b>0;b>>=1,a=1ll*a*a%mod)if(b&1)res=1ll*res*a%mod;
	return res;
}

int tt,n=100000,m,a[100009],fac[100009],inv[100009],A[NR],B[NR],rev[NR],lim,bit;

void NTT(int *a,int type){
	for(int i=0;i<lim;++i)if(i<rev[i])swap(a[i],a[rev[i]]);
	for(int k=1;k<lim;k<<=1){
		int wn=powmod(type==1?g:gi,(mod-1)/(k<<1));
		for(int i=0;i<lim;i+=(k<<1)){
			int w=1;
			for(int j=0;j<k;++j,w=1ll*w*wn%mod){
				int x=a[i+j],y=1ll*w*a[i+j+k]%mod;
				a[i+j]=(x+y)%mod,a[i+j+k]=(x-y+mod)%mod;
			}
		}
	}
	if(type==1)return ;
	int invn=powmod(lim,mod-2);
	for(int i=0;i<lim;++i){
		a[i]=1ll*a[i]*invn%mod;
	}
}



void cdq(int l,int r){
	//cerr<<l<<"::"<<r<<"\n";
	if(l==r){
		//cout<<l<<"::"<<fac[l]<<"__"<<a[l]<<"\n";
		a[l]=(fac[l]-a[l]+mod)%mod;
		return ;
	}
	int mid=(l+r)>>1;
	cdq(l,mid);
	lim=1,bit=0;
	while(lim<=(r-l+1)*2)lim<<=1,bit+=1;
	for(int i=0;i<lim;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
	for(int i=0;i<lim;++i)A[i]=B[i]=0;
	for(int i=l;i<=mid;++i)A[i-l]=a[i];
	for(int i=0;i<=r-l+1;++i)B[i]=fac[i];
	NTT(A,1),NTT(B,1);
	for(int i=0;i<lim;++i)A[i]=1ll*A[i]*B[i]%mod;
	NTT(A,0);
	for(int i=mid+1;i<=r;++i)a[i]=(a[i]+A[i-l])%mod;
	cdq(mid+1,r);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    fac[0]=inv[0]=1;
    for(int i=1;i<=n;++i)fac[i]=1ll*fac[i-1]*i%mod;
    inv[n]=powmod(fac[n],mod-2);
	for(int i=n-1;i;--i)inv[i]=1ll*inv[i+1]*(i+1)%mod;
	a[0]=1;
	cdq(0,n);
	cin>>tt;
    f(sb,1,tt){
    	ll ans=1;
    	cin>>n>>m;
    	for(int i=1,x,mi,ma;i<=m;++i){
    		cin>>x;
    		mi=0x3f3f3f,ma=-1;
    		for(int j=1,y;j<=x;++j){
    			cin>>y;
    			mi=min(mi,y),ma=max(ma,y);
    		}
    		if(ma-mi+1!=x)ans=0;
    		else ans=1ll*ans*a[ma-mi+1]%mod;
    	}
    	cout<<ans<<"\n";
    }
    return 0;
}

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

脑阔疼的dp:)

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
#include <bits/stdc++.h>
/*
#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 scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#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;

using ll=long long;
const int mod=998244353,g=3,gi=332748118,NR=1<<21;
int n=1e5,a[NR],fac[(int)1e5+9],inv[(int)1e5+9],rev[NR],A[NR],B[NR],lim,bit;
int powmod(int a,int b){
	int res=1;
	for(;b>0;b>>=1,a=1ll*a*a%mod)if(b&1)res=1ll*res*a%mod;
	return res;
}

void NTT(int *a,int type){
	for(int i=0;i<lim;++i)if(i<rev[i])swap(a[i],a[rev[i]]);
	for(int k=1;k<lim;k<<=1){
		int wn=powmod(type==1?g:gi,(mod-1)/(k<<1));
		for(int i=0;i<lim;i+=(k<<1)){
			int w=1;
			for(int j=0;j<k;++j,w=1ll*w*wn%mod){
				int x=a[i+j],y=1ll*w*a[i+j+k]%mod;
				a[i+j]=(x+y)%mod,a[i+j+k]=(x-y+mod)%mod;
			}
		}
	}
	if(type==1)return ;
	int invn=powmod(lim,mod-2);
	for(int i=0;i<lim;++i){
		a[i]=1ll*a[i]*invn%mod;
	}
}

void cdq(int l,int r){
	if(l==r)return ;
	int mid=(l+r)>>1;
	cdq(l,mid);
	lim=1,bit=0;
	while(lim<=(r-l+1)*2)lim<<=1,bit+=1;
	for(int i=0;i<lim;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
	for(int i=0;i<lim;++i)A[i]=B[i]=0;
	for(int i=l;i<=mid;++i)A[i-l]=1ll*a[i]*inv[i]%mod;
	for(int i=1;i<=r-l;++i)B[i]=1ll*i*i%mod;
	NTT(A,1),NTT(B,1);
	for(int i=0;i<lim;++i)A[i]=1ll*A[i]*B[i]%mod;
	NTT(A,0);
	for(int i=mid+1;i<=r;++i)a[i]=(a[i]+1ll*A[i-l]*fac[i-1]%mod)%mod;
	cdq(mid+1,r);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    fac[0]=fac[1]=inv[0]=1;
    for(int i=2;i<=n;++i)fac[i]=1ll*fac[i-1]*i%mod;
    inv[n]=powmod(fac[n],mod-2);
	for(int i=n-1;i;--i)inv[i]=1ll*inv[i+1]*(i+1)%mod;
    a[0]=1;
	cdq(0,n);
	while(~scanf("%d",&n))printf("%d\n",a[n]);
    return 0;
}

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

首先固定的起始坐标,然后找的个数，存到中，两遍前缀和。

接着就是找和了，不妨设的起始坐标为，则的长度为，注意。

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
#include <bits/stdc++.h>
/*
#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 scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#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;

using ll=long long;

ll tt,f[(int)5e3+9][(int)5e3+9],ans[(int)5e3+9][(int)5e3+9];
const int P=31;
//ull hashs[(int)5e3+9],po[(int)5e3+9]={1};
//ull gethash(int l,int r){return hashs[r]-hashs[l-1]*po[r-l+1];}

char s[(int)5e3+9];
int main()
{
    scanf("%lld",&tt);
    for(int i=1;i<=tt;++i){
    	scanf("%s",s+1);
    	int len=strlen(s+1);
    	for(int i=1;i<=len+1;++i){
    		for(int j=1;j<=len+1;++j)ans[i][j]=f[i][j]=0;
    	}
    	for(int i=len;i;--i)for(int j=len;j>=i;--j){
    		if(s[i]==s[j])f[i][j]=f[i+1][j+1]+1;
    		else f[i][j]=0;
    	}
    	ll res=0;
    	for(int i=1;i<=len;++i)for(int j=i+1;j<=len;++j){
    		if(f[i][j]>=j-i)ans[j][j-i]+=1;
    	}
        for(int i=1;i<=len;++i){
            for(int j=1;j<=len;++j)ans[i][j]+=ans[i][j-1];
            for(int j=1;j<=len;++j)ans[i][j]+=ans[i][j-1];
        }
        for(int i=1;i<=len;++i){
            for(int j=i+3;j<=len;++j){
                ll qsb=min(j-i-1ll,f[i][j]);
                if(qsb>=2){
                    res+=ans[i][qsb-1];
                }
            }
        }
    	printf("%lld\n",res);
    }
    return 0;
}

发表于 更新于 分类于 本文字数： 274 阅读时长 ≈ 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
#include <bits/stdc++.h>
/*
#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 scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#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;

using ll=long long;

ll n,m,x,y,a[(int)2e5+9],ans,lstd,lstw=-10086;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>x>>y; 
    for(int i=1;i<=m;++i)cin>>a[i];
    a[m+1]=n+1;
    for(int i=1;i<=m+1;++i){
        ll wk=a[i]-1-a[i-1];
        if(a[i-1]-lstw==1&&wk+lstd>y){
            wk-=(y-lstd+1),ans+=1;
            ans+=wk/(y+2ll)*2ll,wk%=(y+2ll);
            if(wk>lstd){
                ans+=1,wk-=(lstd+1);
            }
        }
        if(wk>x){
            if(2ll*x<=y){
                ans+=wk/(x+1ll),wk=wk%(x+1ll);
                if(wk==0)lstw=a[i]-2;
                else lstw=a[i]-1;
            }else{
                ans+=wk/(y+2ll)*2ll,wk%=(y+2ll);
                if(wk==0)lstw=a[i]-2;
                else{
                    if(wk>x){
                        ans+=1,wk-=(x+1);
                        if(wk==0)lstw=a[i]-2;
                        else lstw=a[i]-1;
                    }else lstw=a[i]-1;
                }
            }
        }else lstw=a[i]-1;
        lstd=wk;
    }
    cout<<ans;
    return 0;
}

发表于 更新于 分类于 本文字数： 312 阅读时长 ≈ 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
#include <bits/stdc++.h>
/*
#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 scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#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;

using ll=long long;

ll n,phi[(int)1e5+9],pr[(int)1e5+9],ans,cnt;
const int mod=1e9+7;
bitset<(int)1e5+9> vis;
ll gcd(ll ma,ll mi){return mi?gcd(mi,ma%mi):ma;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
void getphi(int x){
	vis.set();
	phi[1]=1;
	for(int i=2;i<=x;++i){
		if(vis[i]){
			phi[i]=i-1,pr[++cnt]=i;
		}
		for(int j=1;j<=cnt&&i*pr[j]<=x;++j){
			vis[i*pr[j]]=0;
			if(i%pr[j]==0){
				 phi[i * pr[j]] = phi[i] * pr[j]; 
				 break;
			}else phi[i*pr[j]]= phi[i] * phi[pr[j]];
		}
	}
	phi[1]=0;
}

vi factors(int x){
	set<int>s;
	for(int i=1;i*i<=x;++i){
		if(x%i==0)s.insert(i);
		if(x%i==0&&x%(x/i)==0)s.insert(x/i);
	}
	return vector<int>(s.begin(), s.end());
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    getphi(n);
    for(int i=1;i<n;++i){
    	for(auto it:factors(n-i)){
    		ans=(ans+lcm(i,it)*phi[(n-i)/it])%mod;
    	}
    }
    cout<<ans;
    return 0;
}
0%