Codeforces Round #589 (Div. 2)

A. Distinct Digits

time limit per test1 second memory limit per test256 megabytes

You have two integers ?l and ?r. Find an integer ?x which satisfies the conditions below:

  • ?≤?≤?l≤x≤r.
  • All digits of ?x are different.

If there are multiple answers, print any of them.Input

The first line contains two integers ?l and ?r (1≤?≤?≤1051≤l≤r≤105).Output

If an answer exists, print any of them. Otherwise, print −1−1.

Examplesinput

121 130

output

123

input

98766 100000

output

-1

Note

In the first example, 123123 is one of the possible answers. However, 121121 can't be the answer, because there are multiple 11s on different digits.

In the second example, there is no valid answer.

签到

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
bool ck(int x){
    set<int> s;
    int num=0;
    while(x){
        num++;
        s.insert(x%10);
        x/=10;
    }
    return s.size()==num;
}
int main(){
    int l,r;cin>>l>>r;
    rep(i,l,r) if(ck(i)) return printf("%d\n",i),0;
    printf("-1\n");
}


B. Filling the Grid

time limit per test1 second memory limit per test256 megabytes

Suppose there is a ℎ×?h×w grid consisting of empty or full cells. Let's make some definitions:

  • ??ri is the number of consecutive full cells connected to the left side in the ?i-th row (1≤?≤ℎ1≤i≤h). In particular, ??=0ri=0 if the leftmost cell of the ?i-th row is empty.
  • ??cj is the number of consecutive full cells connected to the top end in the ?j-th column (1≤?≤?1≤j≤w). In particular, ??=0cj=0 if the topmost cell of the ?j-th column is empty.

In other words, the ?i-th row starts exactly with ??ri full cells. Similarly, the ?j-th column starts exactly with ??cj full cells.

These are the ?r and ?c values of some 3×43×4 grid. Black cells are full and white cells are empty.

You have values of ?r and ?c. Initially, all cells are empty. Find the number of ways to fill grid cells to satisfy values of ?r and ?c. Since the answer can be very large, find the answer modulo 1000000007(109+7)1000000007(109+7). In other words, find the remainder after division of the answer by 1000000007(109+7)1000000007(109+7).Input

The first line contains two integers ℎh and ?w (1≤ℎ,?≤1031≤h,w≤103) — the height and width of the grid.

The second line contains ℎh integers ?1,?2,…,?ℎr1,r2,…,rh (0≤??≤?0≤ri≤w) — the values of ?r.

The third line contains ?w integers ?1,?2,…,??c1,c2,…,cw (0≤??≤ℎ0≤cj≤h) — the values of ?c.Output

Print the answer modulo 1000000007(109+7)1000000007(109+7).ExamplesinputCopy

3 4
0 3 1
0 2 3 0

outputCopy

2

inputCopy

1 1
0
1

outputCopy

0

inputCopy

19 16
16 16 16 16 15 15 0 5 0 4 9 9 1 4 4 0 8 16 12
6 12 19 15 8 6 19 19 14 6 9 16 10 11 15 4

outputCopy

797922655

Note

In the first example, this is the other possible case.

In the second example, it's impossible to make a grid to satisfy such ?r, ?c values.

In the third example, make sure to print answer modulo (109+7)(109+7).

扫一遍标记一下就好了

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e3+100;
const int mod=(int)1e9+7;
int n,m,a[maxn],b[maxn],mp[maxn][maxn];
ll qpow(ll base,ll n){
    ll res=1;
    while(n){
        if(n&1) res=res*base%mod;
        base=base*base%mod;
        n>>=1;
    }
    return res;
}
int main(){
    cin>>n>>m;
    rep(i,1,n) scanf("%d",&a[i]);
    rep(i,1,m) scanf("%d",&b[i]);
    rep(i,1,n){
        rep(j,1,a[i]) mp[i][j]=1;
        mp[i][a[i]+1]=2;
    }
    rep(i,1,m){
        rep(j,1,b[i]){
            if(mp[j][i]==2) return puts("0"),0;
            mp[j][i]=1;
        }
        if(mp[b[i]+1][i]==1) return puts("0"),0;
        mp[b[i]+1][i]=2;
    }
    int ans=0;
    rep(i,1,n) rep(j,1,m) if(mp[i][j]==0) ans++;
    printf("%lld\n",qpow(2,ans));
}


C. Primes and Multiplication

time limit per test1 second memory limit per test256 megabytes

Let's introduce some definitions that will be needed later.

Let ?????(?)prime(x) be the set of prime divisors of ?x. For example, ?????(140)={2,5,7}prime(140)={2,5,7}, ?????(169)={13}prime(169)={13}.

Let ?(?,?)g(x,p) be the maximum possible integer ??pk where ?k is an integer such that ?x is divisible by ??pk. For example:

  • ?(45,3)=9g(45,3)=9 (4545 is divisible by 32=932=9 but not divisible by 33=2733=27),
  • ?(63,7)=7g(63,7)=7 (6363 is divisible by 71=771=7 but not divisible by 72=4972=49).

Let ?(?,?)f(x,y) be the product of ?(?,?)g(y,p) for all ?p in ?????(?)prime(x). For example:

  • ?(30,70)=?(70,2)⋅?(70,3)⋅?(70,5)=21⋅30⋅51=10f(30,70)=g(70,2)⋅g(70,3)⋅g(70,5)=21⋅30⋅51=10,
  • ?(525,63)=?(63,3)⋅?(63,5)⋅?(63,7)=32⋅50⋅71=63f(525,63)=g(63,3)⋅g(63,5)⋅g(63,7)=32⋅50⋅71=63.

You have integers ?x and ?n. Calculate ?(?,1)⋅?(?,2)⋅…⋅?(?,?)mod(109+7)f(x,1)⋅f(x,2)⋅…⋅f(x,n)mod(109+7).Input

The only line contains integers ?x and ?n (2≤?≤1092≤x≤109, 1≤?≤10181≤n≤1018) — the numbers used in formula.Output

Print the answer.

Examplesinput

10 2

output

2

input

20190929 1605

output

363165664

input

947 987654321987654321

output

593574252

Note

In the first example, ?(10,1)=?(1,2)⋅?(1,5)=1f(10,1)=g(1,2)⋅g(1,5)=1, ?(10,2)=?(2,2)⋅?(2,5)=2f(10,2)=g(2,2)⋅g(2,5)=2.

In the second example, actual value of formula is approximately 1.597⋅101711.597⋅10171. Make sure you print the answer modulo (109+7)(109+7).

In the third example, be careful about overflow issue.

质因数分解后算贡献

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const int mod=(int)1e9+7;
vector<long long >q;
bool check[maxn];
int prime[maxn];
int min_prime[maxn];
int Prime(int n){
    memset(check,true,sizeof(check));
    int sum=0,i,j;
    for(i=2;i<=n;i++){
        if(check[i])
            prime[sum++]=i;
        for(j=0;j<sum&&i*prime[j]<=n;j++){
            check[i*prime[j]]=false;
            min_prime[i*prime[j]]=prime[j];
            if(i%prime[j]==0)
                break;
        }
    }
    return sum;
}
int is(long long n){
   for(long long i=2;i<=sqrt(n);i++){
   	 if(n%i==0) return 0;
   }	
   return 1;
}
long long cal(long long base,long long n){
    long long res = 1;
    while (n > 0){
        if (n & 1)
         res = (res * base) % mod;
        base = (base * base) % mod;
        n >>= 1;
    }
    return res;
}
int main(){
   Prime(100000+10);
   int x;long long n;
   cin>>x>>n;
   if(is(x)) q.push_back(x);
   else{
   	   int temp=x;
	   for(int i=2;i<=sqrt(x);i++){
	   	  if(check[i]==1){
	   	     if(temp%i==0) q.push_back(i);
		     while(temp%i==0) temp/=i; 	
		  }
	   }
	   if(is(temp)&&temp!=1) q.push_back(temp);
   }
   long long ans=1;
   for(int i=0;i<q.size();i++){
   	 long long temp=n;long long tot=0;
   	 while(temp>0){
   	 	tot+=temp/q[i];
   	 	temp/=q[i];
	 }
	 ans=(ans*cal(q[i],tot))%mod;
   }
   cout<<ans<<endl;
   
}


D. Complete Tripartite

time limit per test2 seconds memory limit per test256 megabytes

You have a simple undirected graph consisting of ?n vertices and ?m edges. The graph doesn't contain self-loops, there is at most one edge between a pair of vertices. The given graph can be disconnected.

Let's make a definition.

Let ?1v1 and ?2v2 be two some nonempty subsets of vertices that do not intersect. Let ?(?1,?2)f(v1,v2) be true if and only if all the conditions are satisfied:

  1. There are no edges with both endpoints in vertex set ?1v1.
  2. There are no edges with both endpoints in vertex set ?2v2.
  3. For every two vertices ?x and ?y such that ?x is in ?1v1 and ?y is in ?2v2, there is an edge between ?x and ?y.

Create three vertex sets (?1v1, ?2v2, ?3v3) which satisfy the conditions below;

  1. All vertex sets should not be empty.
  2. Each vertex should be assigned to only one vertex set.
  3. ?(?1,?2)f(v1,v2), ?(?2,?3)f(v2,v3), ?(?3,?1)f(v3,v1) are all true.

Is it possible to create such three vertex sets? If it's possible, print matching vertex set for each vertex.Input

The first line contains two integers ?n and ?m (3≤?≤1053≤n≤105, 0≤?≤min(3⋅105,?(?−1)2)0≤m≤min(3⋅105,n(n−1)2)) — the number of vertices and edges in the graph.

The ?i-th of the next ?m lines contains two integers ??ai and ??bi (1≤??<??≤?1≤ai<bi≤n) — it means there is an edge between ??ai and ??bi. The graph doesn't contain self-loops, there is at most one edge between a pair of vertices. The given graph can be disconnected.Output

If the answer exists, print ?n integers. ?i-th integer means the vertex set number (from 11 to 33) of ?i-th vertex. Otherwise, print −1−1.

If there are multiple answers, print any.ExamplesinputCopy

6 11
1 2
1 3
1 4
1 5
1 6
2 4
2 5
2 6
3 4
3 5
3 6

outputCopy

1 2 2 3 3 3 

inputCopy

4 6
1 2
1 3
1 4
2 3
2 4
3 4

outputCopy

-1

Note

In the first example, if ?1={1}v1={1}, ?2={2,3}v2={2,3}, and ?3={4,5,6}v3={4,5,6} then vertex sets will satisfy all conditions. But you can assign vertices to vertex sets in a different way; Other answers like "2 3 3 1 1 1" will be accepted as well.

In the second example, it's impossible to make such vertex sets.

一个点走两步到达点点必定与自己在一个集合内,于是可以构造出三个点集,再暴力判一下合理性就可以了

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
vector<int> g[maxn];
int a[maxn];
struct node{int x,y;} p[maxn*3];
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        p[i]={x,y};
        g[x].pb(y);g[y].pb(x);
    }
    for (int i=1;i<=n;i++) a[i]=1;
    for (auto i:g[1]) a[i]=0;
    int kk;
    for (int i=1;i<=n;i++) if(!a[i]) {kk=i;break;}
    a[kk]=2;
    for (auto i:g[kk]) if(!a[i]) a[i]=3;
    for (int i=1;i<=n;i++) if(!a[i]) a[i]=2;
    int s1=0,s2=0,s3=0;
    int k1=0,k2=0,k3=0;
    for (int i=1;i<=n;i++) 
    {
        if(a[i]==1) {s1++;k1+=g[i].size();}
        if(a[i]==2) {s2++;k2+=g[i].size();}
        if(a[i]==3) {s3++;k3+=g[i].size();}
    }
    int flag=1;
    if(!s1 || !s2 || !s3) flag=0;
    if(s1+s2+s3!=n) flag=0;
    if(k1!=s1*(s2+s3) || k2!=s2*(s1+s3) || k3!=s3*(s1+s2)) flag=0;
    for (int i=1;i<=m;i++) 
        if(a[p[i].x]==a[p[i].y]) {flag=0;break;}
    if(!flag) printf("-1\n");
    else
    {
        for (int i=1;i<=n;i++) printf("%d ",a[i]);
        printf("\n");
    }
    return 0;
}


E. Another Filling the Grid

time limit per test1 second memory limit per test256 megabytes

You have ?×?n×n square grid and an integer ?k. Put an integer in each cell while satisfying the conditions below.

  • All numbers in the grid should be between 11 and ?k inclusive.
  • Minimum number of the ?i-th row is 11 (1≤?≤?1≤i≤n).
  • Minimum number of the ?j-th column is 11 (1≤?≤?1≤j≤n).

Find the number of ways to put integers in the grid. Since the answer can be very large, find the answer modulo (109+7)(109+7).

These are the examples of valid and invalid grid when ?=?=2n=k=2.Input

The only line contains two integers ?n and ?k (1≤?≤2501≤n≤250, 1≤?≤1091≤k≤109).Output

Print the answer modulo (109+7)(109+7).ExamplesinputCopy

2 2

outputCopy

7

inputCopy

123 456789

outputCopy

689974806

Note

In the first example, following 77 cases are possible.

In the second example, make sure you print the answer modulo (109+7)(109+7).

\(n^3\) dp,\(dp[i][j]\)表示填完前\(i\)行,有\(j\)列最小值为1的方案数,那么转移就是\(dp[i][j]=\sum_{m=0}^{j}C[n-m][j-m] \times dp[i-1][j] \times (k-1)^{n-j} \times k^m\);

其中,\(C[n-m][j-m]\)表示从多出来的\(n-m\)列中任选\(j-m\)列填1;
\((k-1)^(n-j)\) 是保证没有1的列不能填1,只有k−1种填的数;
\(k^m\)保证原有1的列随便填什么都可以;
需要注意一下最后\(j==m\)的情况需要特殊判断;

预处理出k和k-1的幂次可以降为\(n^3\)

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)3e3+100;
const ll mod=(ll)1e9+7;
ll n,k,dp[maxn][maxn],C[maxn][maxn];
ll k1[maxn],k2[maxn];
ll Mod(ll a){return a>=mod?a-mod:a;}
int main(){
	scanf("%lld%lld",&n,&k);
	k1[0]=k2[0]=1;
	rep(i,0,n){ //预处理
		C[i][0]=1;
		rep(j,1,i) C[i][j]=Mod(C[i-1][j]+C[i-1][j-1]);
		if(i){
			k1[i]=k1[i-1]*k%mod;
			k2[i]=k2[i-1]*(k-1)%mod;
		}
	}
	rep(i,1,n) dp[1][i]=C[n][i]*k2[n-i]%mod;
	rep(i,2,n) rep(j,0,n) rep(m,0,j){
		dp[i][j]=Mod(dp[i][j]+C[n-m][j-m]*dp[i-1][m]%mod*k2[n-j]%mod*k1[m]%mod);
		if(j==m) dp[i][j]=Mod(dp[i][j]-k2[n]*dp[i-1][j]%mod+mod);
	}
	printf("%d\n",dp[n][n]);
}

Subscribe
提醒
0 评论
Inline Feedbacks
View all comments