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]);
}

发表评论,支持MarkDown语法