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:
- There are no edges with both endpoints in vertex set ?1v1.
- There are no edges with both endpoints in vertex set ?2v2.
- 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;
- All vertex sets should not be empty.
- Each vertex should be assigned to only one vertex set.
- ?(?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]);
}
