Liens du Concours
Les performances d'AtCoder varient l'après-midi, mais les soirées de compétition sont toujours exceptionnelles.
A - Redondance Redondante
Étant donné un entier \(N(2\leq N\leq 30)\), trouver un entier \(x(N\leq x\leq 10^{13})\) tel que pour tout entier \(y(2\leq y\leq N)\), on ait \(x\bmod y=1\).
Idées & Solution
Problème d'entrée en matière. Une soluiton possible est :
[ans=\prod_{j=2}^nj+1 ]``` //Auteur: RingweEH long long pgcd( long long a,long long b ) { return (b==0) ? a : pgcd( b,a%b ); }
int main() { long long n=lire(),x=1; for ( long long i=2; i<=n; i++ ) { long long gc=pgcd( x,i ); x=x*i/gc; } printf( "%lld\n",x+1 ); }
B - Beaucoup de 110
------------
Soit \\(S\\) le résultat de la répétition de `110` \\(10^{10}\\) fois. Étant donné une chaîne de caractères \\(T\\) de longueur \\(N\\), trouver son nombre d'occurrences.
### Idées & Solution
Petite analyse de cas.
- Pour \\(n\\leq 2\\), juger directement et afficher le résultat
- Pour \\(n>2\\), selon les trois premiers caractères de \\(T\\), déterminer si cela commence à la position 1/2/3 de \\(S\\), puis construire une chaîne `110` \\(str\\) de taille suffisante pour contenir \\(T\\), et faire une correspondance directe ; si possible, soit \\(x\\) le nombre de `110` utilisés dans \\(str\\), la réponse est \\(10^{10}-(x-1)\\). Sinon, la réponse est \\(0\\). Si les trois premiers caractères ne permettent pas de construire une telle chaîne, la réponse est également \\(0\\).
- Voir le code pour plus de détails.
//Auteur: RingweEH const int N=2e5+10; int n; char s[N],str[N+10];
int main() { n=lire(); scanf( "%s",s+1 ); long long cnt=n/3+2; for ( int i=1; i<=cnt*3; i+=3 ) { str[i]='1'; str[i+1]='1'; str[i+2]='0'; } if ( n<=2 ) { if ( n==1 ) { if ( s[1]=='0' ) printf( "10000000000\n" ); else printf( "20000000000\n" ); return 0; } if ( (s[1]=='1') && (s[2]=='1') ) printf( "10000000000\n" ); if ( (s[1]=='1') && (s[2]=='0') ) printf( "10000000000\n" ); if ( (s[1]=='0') && (s[2]=='0') ) printf( "0\n" ); if ( (s[1]=='0') && (s[2]=='1') ) printf( "9999999999\n" ); return 0; } if ( (s[1]=='1') && (s[2]=='1') && (s[3]=='0') ) { for ( int i=1; i<=n; i++ ) if ( s[i]!=str[i] ) { printf( "0\n" ); return 0; } if ( n%3 ) cnt=n/3+1; else cnt=n/3; printf( "%lld\n",10000000000-(cnt-1) ); return 0; } else if ( (s[1]=='1') && (s[2]=='0') && (s[3]=='1') ) { for ( int i=2; i<=n+1; i++ ) if ( str[i]!=s[i-1] ) { printf( "0\n" ); return 0; } cnt=((n+1)%3) ? (n+1)/3+1 : (n+1)/3; printf( "%lld\n",10000000000-(cnt-1) ); return 0; } else if ( (s[1]=='0') && (s[2]=='1') && (s[3]=='1') ) { for ( int i=3; i<=n+2; i++ ) if ( str[i]!=s[i-2] ) { printf( "0\n" ); return 0; } cnt=((n+2)%3) ? (n+2)/3+1 : (n+2)/3; printf( "%lld\n",10000000000-(cnt-1) ); return 0; } else { printf( "0\n" ); return 0; } }
C - Échange Extérieur
-----------
Étant donné une permutation \\(P=P_1,P_2,\dots ,P_N\\) de longueur \\(N\\).
Vous devez effectuer les \\(N-1\\) opérations suivantes dans un ordre quelconque, chacune **exactement une fois** :
- Échanger \\(P_i,P_{i+1}(i=1\\sim n-1)\\) .
Déterminer s'il est possible de trier \\(P\\) en ordre croissant, sinon afficher -1, sinon donner une solution.
### Idées & Solution
Approche inhabituelle mais correcte développée pendant la compétition...
Il est déconseillé de consulter cette solution, car elle représente une approche développée dans l'urgence pendant la compétition (bien que correcte, la logique du code est quelque peu étrange).
- L'échange de deux éléments adjacents modifie le nombre d'inversions de 1. Ainsi, si le nombre total d'inversions dépasse \\(n\\), c'est manifestement impossible.
- S'il existe trois éléments consécutifs en ordre décroissant, c'est manifestement impossible.
- Pour toutes les paires d'inversions consécutives \\(P_i>P_{i+1}\\), placer \\(i\\) dans une file et traiter successivement :
- Choisir l'élément en tête de file ; s'il forme toujours une paire d'inversion, échanger, et incrémenter \\(cnt\\) ;
- Vérifier l'élément précédent et le suivant ; s'ils forment une nouvelle paire d'inversion, les ajouter à la file ;
- Vérifier si exactement \\(n-1\\) échanges ont été effectués et si tous les éléments sont à leur place finale.
//Auteur: RingweEH #define lowbit(x) ((x)&(-x)) #define PII pair<int,int> const int N=2e5+10; int n,p[N],c[N],ans[N]; queue q;
void ajouter( int x,int val ) { for ( ; x<=n; x+=lowbit(x) ) c[x]++; } int somme_prefixe( int x ) { int res=0; for ( ; x; x-=lowbit(x) ) res+=c[x]; return res; }
int main() { n=lire(); for ( int i=1; i<=n; i++ ) p[i]=lire();
int cnt=0;
for ( int i=n; i>=1; i-- )
{
cnt+=somme_prefixe( p[i]-1 );
if ( cnt>n ) { printf( "-1" ); return 0; }
ajouter( p[i],1 );
}
if ( cnt>n ) { printf( "-1" ); return 0; }
for ( int i=1; i<n-1; i++ )
if ( (p[i]>p[i+1]) && (p[i+1]>p[i+2]) ) { printf( "-1" ); return 0; }
for ( int i=1; i<n; i++ )
if ( (p[i]>p[i+1]) ) q.push( i );
cnt=0;
while ( !q.empty() )
{
int u=q.front(); q.pop();
if ( p[u]>p[u+1] ) swap( p[u],p[u+1] ),ans[++cnt]=u;
if ( (u>1) && (p[u-1]>p[u]) ) q.push( u-1 );
if ( (u<n-1) && (p[u+1]>p[u+2]) ) q.push( u+1 );
}
if ( cnt!=(n-1) ) { printf( "-1" ); return 0; }
for ( int i=1; i<=n; i++ )
if ( p[i]!=i ) { printf( "-1" ); return 0; }
for ( int i=1; i<n; i++ )
printf( "%d\n",ans[i] );
}
D - Le Coefficient Binomial est Amusant
-------------------------------
Étant donné une séquence d'entiers non négatifs \\(A\\) de longueur \\(n\\).
Pour toutes les séquences \\(B\\) satisfaisant \\(\\sum_i B_i\\leq M,B_i\\in N\\), calculer la somme de $$\\prod_{i=1}^n {B_i\\choose A_i}$$ modulo \\(1e9+7\\).
\\(1\\leq N\\leq 2000,1\\leq M\\leq 1e9,0\\leq A_i\\leq 2000\\) .
### Idées & Solution
Approche standard : sous-problème où \\(\\sum B_i=M\\).
Comme nous cherchons un produit, seule les séquences où \\(B_i\\ge A_i\\) contribuent.
Considérons la signification combinatoire de ce problème, où \\(B\\) représente \\(M\\) boules. Comme la valeur de \\(B_i\\) peut varier, considérons l'ajout de \\(N-1\\) séparateurs pour délimiter \\(B_i,B_{i+1}\\).
Ensuite, plaçons \\(A\\). En exploitant la flexibilité de \\(B\\), nous pouvons utiliser \\(A\\) pour déterminer la position des séparateurs, c'est-à-dire :
- Sélectionner au total \\(\\sum A_i+N-1\\) positions parmi \\(M+N-1\\) ;
- Les positions \\(1\\sim A_1\\) représentent \\(A_1\\), la position \\(A_1+1\\) est le premier séparateur, et ainsi de suite.
- La valeur de \\(B_i\\) varie avec la position des séparateurs et est toujours valide.
Le problème se transforme en sélectionner \\(\\sum A_i+N-1\\) positions parmi \\(M+N-1\\), la solution du sous-problème étant :
\[ans_{sub}={ M+N-1\\choose\\sum A_i+N-1} \]Examinons maintenant la solution finale.
\[ans=\sum_{i=\sum A_j}^M {i+N-1\\choose \sum A_j+N-1}\\ =\sum_{i=\sum A_j+N-1}^{M+N-1}{i\\choose \sum A_j+N-1}\\ \because \sum_{i=k}^n{i\\choose k}={n+1\\choose k+1 }\\ \therefore ans={M+N\\choose \sum A_j+N} \]```
//Auteur: RingweEH
const long long Mod=1e9+7;
long long n,m;
long long puissance( long long a,long long b )
{
long long res=1;
for ( ; b; b>>=1,a=a*a%Mod )
if ( b&1 ) res=res*a%Mod;
return res;
}
int main()
{
n=lire(); m=lire(); int somme=0;
for ( int i=1; i<=n; i++ )
somme=somme+lire();
if ( m<somme ) { printf( "0\n" ); return 0; }
m+=n; somme+=n;
long long ans=1;
for ( long long i=1; i<=somme; i++ )
ans=ans*puissance( i,Mod-2 )%Mod*(m-i+1)%Mod;
printf( "%lld\n",ans );
}
E - Raccourcir ABC
Étant donné une chaîne de caractères \(s\) contenant uniquement ABC, à chaque étape, on peut choisir deux caractères adjacents différents et les remplacer par le troisième caractère.
Déterminer le nombre de chaînes de caractères différentes possibles après un nombre quelconque d'opérations (y compris zéro), modulo \(1e9+7\). \(|S|\leq 1e6\) .
Idées & Solution
Soit A, B, C représentés par \(1,2,3\) respectivement. Sans considérer la restriction que les caractères adjacents doivent être différents, cette "fusion" équivaut à remplacer \(x,y\) par \(x\oplus y\).
Pour la restriction \(x\neq y\), on peut prouver par induction que cela équivaut à ce que la somme XOR de l'intervalle ne soit pas \(0\) et que les caractères de l'intervalle ne soient pas tous identiques ou que la longueur de l'intervalle soit \(1\).
Ainsi, le problème revient à diviser la séquence originale en plusieurs intervalles et à calculer la valeur XOR de chacun.
Pour éviter de compter plusieurs fois le même schéma, nous imposons que, hormis le premier intervalle, tout préfixe non vide de tout intervalle ait une somme XOR non nulle, sinon ce préfixe pourrait être ajouté à l'intervalle précédent.
Soit \(f[i]\) le nombre de façons de partitionner les \(i\ premiers éléments. L'équation de transition est :
Soit \(nxt[i]\) la première occurrence de \(j\) dans \(i+1\sim n\) telle que \(suma[i]=suma[j]\), où \(suma\) représente la somme préfixe XOR.
[f[i]=>f[i+1],\dots,f[nxt[i]-1] ]Cette partie peut être maintenue avec une différence.
//Auteur: RingweEH
const int N=1e6+10;
const long long Mod=1e9+7;
int n,a[N],dernier[5],suivant[N];
long long f[N];
char s[N];
void ajouter( int l,int r,long long val )
{
f[l]=(f[l]+val)%Mod;
if ( r+1<=n ) f[r+1]=(f[r+1]+Mod-val)%Mod;
}
int main()
{
n=lire(); scanf( "%s",s+1 );
a[0]=0; bool valide=0;
for ( int i=1; i<=n; i++ )
{
if ( s[i]=='A' ) a[i]=1;
else if ( s[i]=='B' ) a[i]=2;
else a[i]=3;
if ( (a[i]^a[i-1]) && (i>1) ) valide=1;
}
if ( !valide ) { printf( "1\n" ); return 0; } //Vérifier si tous les caractères sont identiques
for ( int i=1; i<=n; i++ )
a[i]^=a[i-1];
for ( int i=0; i<5; i++ )
dernier[i]=n+1;
for ( int i=n; i>=1; i-- )
suivant[i]=dernier[a[i]],dernier[a[i]]=i;
for ( int i=1; i<=n; i++ )
if ( a[i] ) ajouter( i,i,1 );
for ( int i=1; i<=n; i++ )
{
if ( i>1 ) f[i]=(f[i]+f[i-1])%Mod;
ajouter( i+1,suivant[i]-1,f[i] );
}
printf( "%lld\n",f[n] );
return 0;
}
F - Échange Éso
Étant donné une permutation \(P=P_0,\dots,P_{N-1}\) de longueur \(N(2\leq N\leq 100)\). Vous pouvez effectuer l'opération suivante au plus \(2e5\) fois :
- Choisir un indice \(i(0\leq i\leq N-1)\), échanger \(P_i,P(i+P_i)\bmod N\)
Si la permutation finale ne peut pas être triée en ordre croissant, afficher -1, sinon donner une solution.
Idées & Solution
Observons d'abord les exemples.
8
7 1 2 6 4 0 5 3
On remarque une approche très simple : opérer sans réfléchir sur la position \(0\).
7 1 2 6 4 0 5 3
3 1 2 6 4 0 5 7
6 1 2 3 4 0 5 7
5 1 2 3 4 0 6 7
0 1 2 3 4 5 6 7
Considérons la position \(0\) : chaque nombre qui y est placé est renvoyé à sa position finale, et cette transformation ne se répète jamais (évidemment, car la valeur de \(P\) à cette position ne peut pas être la même à chaque fois). Une fois que \(0\) est à sa place, le processus se termine.
De plus, on constate que cette propriété s'applique à toutes les positions, sauf pour la première.
Ensuite, considérons la construction suivante :
- De \(n-1\sim 1\) en ordre décroissant, opérer pour que \(p[i]=n-1-i\).
Preuve
Lorsque vous opérez sur la position \(i\), vous avez déjà fixé les éléments \(i+1\sim n-1\), et les nombres dans \([0,n-i-1]\) sont déjà en place, donc l'opération ne perturbe pas l'ordre des nombres déjà fixés.
En raison de la propriété mentionnée ci-dessus, les transformations ne se répètent pas, donc le nombre d'opérations pour cette partie est au plus \(n^2\).
- Maintenant, tous les nombres sont en ordre décroissant. Considérons utiliser la position \(1\) pour réorganiser.
- Supposons que nous ayons maintenant une forme "ordre décroissant + \(0\ 1\) + ordre croissant". Alors, nous pouvons déplacer \(1\) à la fin, puis l'échanger avec les éléments précédents pour insérer le nombre suivant.
- Exemple :
7 6 5 4 0 1 2 3 => 7 6 5 4 0 2 1 3 => 7 6 5 4 0 2 3 1 (échanger 1)
7 6 5 1 0 2 3 4 => 7 6 5 0 1 2 3 4 (insérer)
Le problème est alors résolu.Qu'en est-il des cas sans solution ?
//Auteur: RingweEH
const int N=110;
int n,p[N];
vector<int> reponse;
void Operer( int x )
{
reponse.push_back( x );
swap( p[x],p[(x+p[x])%n] );
}
int main()
{
n=lire();
for ( int i=0; i<n; i++ )
p[i]=lire();
for ( int i=n-1; i; i-- )
while ( p[i]^(n-i-1) ) Operer( i );
for ( int i=n-2; i>=0; i-- )
{
for ( int j=i+1; j<n-1; j++ )
Operer( j );
Operer( i ); Operer( i );
}
printf( "%d\n",reponse.size() );
for ( int i=0 ;i<reponse.size(); i++ )
printf( "%d\n",reponse[i] );
return 0;
}