[PYTHON] concours yukicoder 259 avis
résultat
Impressions
R J'ai senti que le problème était difficile et je me suis enfui. Ce n'est pas difficile si vous suivez les bases, donc je le regrette. Dans le problème B, j'ai fait une erreur dans le temps constant et perdu. Je suis désolé ... Le problème C était une sorte de problème que je n'avais pas fait beaucoup, mais je l'ai résolu. Je suis content d'avoir été collant.
Problème A
(1) La plage de $ t $ dépend de $ D $, et $ D $ est ** extrêmement grande. ** Il est nécessaire de trouver la ** valeur minimale ** $ T $ de ce $ t $. (2) Cela vaut pour $ t <T $. Puisqu'il y a ** monotonie ** qui vaut pour $ t> T $, $ T $ peut être obtenu par dichotomie à cause de ces deux conditions. De plus, si la distance totale parcourue par chaque slime dans un certain $ t $ est calculée par $ O (N) $, le montant du calcul sera $ O (N \ log {D}) $, donc si vous pouvez écrire un programme à temps J'ai pensé.
Considérons maintenant la distance totale de déplacement de tous les slimes en $ t $, mais lorsque les deux slimes (vitesses sont $ v_1 $, $ v_2 $) sont combinés en un slime, la vitesse des slimes restants Le résultat est $ v_1 + v_2 $. Par conséquent, si vous * faites attention à la distance totale parcourue **, cela ne changera pas même si chaque slime ne fusionne pas, donc si vous considérez la distance parcourue par tous les slimes jusqu'à $ t $ (lorsqu'ils ne fusionnent pas), $ O Il peut être calculé par (N) $.
Veuillez également vous référer à cet article pour la dichotomie. De plus, ce problème peut être résolu avec $ O (N) $ au lieu de $ O (N \ log {D}) $ (Main Solution éditorial)).
A.py
n,d=map(int,input().split())
x=list(map(int,input().split()))
v=list(map(int,input().split()))
s=sum(v)
def f(k):
return s*k
#c'est faux,r est vrai
l,r=0,1000000000000
while l+1<r:
k=l+(r-l)//2
if f(k)>=d:
r=k
else:
l=k
print(r)
Problème B
Tout d'abord, vérifiez tous les nombres premiers qui peuvent être déterminés par le tamis Eratostenes ** car la requête est utilisée pour déterminer le nombre premier (cela rend la détermination de la requête première $ O (1) $). S'il est déterminé que $ p $ n'est pas un nombre premier, alors $ -1 $ doit être affiché, donc nous supposerons que $ p $ est un nombre premier et continuerons la discussion ci-dessous.
Sur cette base, si vous demandez simplement $ A ^ {P!} \ (Mod \ P) $ comme $ ((A ^ 1) ^ 2) ^ 3… $, il ne sera pas à temps même sous la condition de $ mod \ P $. Hmm. Ce qu'il faut retenir ici est le ** théorème de Fermat **. Je pense que vous devriez garder à l'esprit qu'il est de notoriété publique dans les problèmes liés à la puissance du $ surplus $. Dans ce théorème, ** $ A ^ {p-1} = 1 \ (mod \ p) $ ** vaut pour $ A $, qui n'est pas un multiple de $ p $ pour le nombre premier $ p $. Ici, $ A ^ {p!} = (A ^ {p-1}) ^ x \ (x = 1,2,…, p-2, p) $ tient, donc ($ \ car \ p $ est $ 2 $ ou plus qu'un nombre premier), $ A ^ {p!} = 0 \ (mod \ P) $ si $ A $ est un multiple de $ p $, $ A ^ {p!} = 1 \ sinon Il devient (mod \ P) $.
Pour résumer ce qui précède, $ -1 $ lorsque $ p $ n'est pas un nombre premier, $ 0 $ lorsque $ p $ est un nombre premier et $ A % p = 0 $, et $ A % p \ lorsque $ p $ est un nombre premier. Lorsque neq 0 $, $ 1 $ doit être affiché.
** J'ai oublié de changer la plage de «MAXRR» dans le code et j'ai émis WA **. C'était douloureux. Cela a pris beaucoup de temps.
B.cc
//Optimisation du compilateur
#pragma GCC optimize("Ofast")
//Inclure etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//macro
//pour boucle
//L'argument est(Variables dans la boucle,Amplitude de mouvement)Ou(Variables dans la boucle,Premier numéro,Nombre d'extrémités)、のどちらOu
//Les variables de boucle sans D sont incrémentées de 1 et les variables de boucle avec D sont décrémentées de 1.
//FORA est une gamme de déclaration(Si c'est difficile à utiliser, effacez-le)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//x est un conteneur tel que vector
#define ALL(x) x.begin(),x.end()
#define SIZE(x) ll(x.size())
//constant
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 6000000 //10^5:Portée maximale de la baie
//Abréviation
#define PB push_back //Insérer
#define MP make_pair //constructeur de paires
#define F first //Le premier élément de paire
#define S second //Le deuxième élément de paire
#define PN true //nombre premier
#define NPN false //Pas un nombre premier
//Non essentiel
#define MAXRR 3000 //√ Définissez un nombre supérieur ou égal à MAXR
//Supposons que les entiers jusqu'à MAXR soient des nombres premiers(Raser d'ici)
vector<bool> PN_chk(MAXR+1,PN);//0index correspond au i-ème entier i(0~MAXR)
//Préparer un tableau pour stocker les nombres premiers
vector<ll> PNs;
void se(){
//0 et 1 ne sont pas des nombres premiers
PN_chk[0]=NPN;PN_chk[1]=NPN;
FOR(i,2,MAXRR){
//Un nombre premier s'il est supposé être un nombre premier à votre arrivée
if(PN_chk[i]) FOR(j,i,ll(MAXR/i)){PN_chk[j*i]=NPN;}
}
FOR(i,2,MAXR){
if(PN_chk[i]) PNs.PB(i);
}
}
ll modpow(ll a,ll n,ll p){
if(n==0)return 1;
ll t=modpow(a,n/2,p);
t=t*t%p;
if(n&1)t=t*a%p;
return t;
}
signed main(){
//Code pour accélérer la saisie
ios::sync_with_stdio(false);
cin.tie(nullptr);
se();
ll t;cin>>t;
REP(_,t){
ll a,p;cin>>a>>p;
if(!PN_chk[p]){
cout<<-1<<endl;
continue;
}
if(a%p==0){
cout<<0<<endl;
continue;
}
cout<<1<<endl;
}
}
Problème C
Si je connaissais le même sujet, je pourrais faire de mon mieux pour le mettre en œuvre, alors j'ai senti le pouvoir de la dévotion.
Premièrement, si vous mettez $ r_i et c_i $ comme indiqué ci-dessous, vous pouvez les diviser en quatre parties ci-dessous.
Sur cette base, nous pouvons voir que la réponse à obtenir est d'obtenir le produit des produits des nombres contenus dans chacun des rectangles ①, ②, ③ et ④. Pour la partie incluse dans un tel rectangle, le traitement des requêtes peut être effectué avec $ O (1) $ en pré-calcul avec ** accumulation bidimensionnelle **.
Lors de la création d'une table par pré-calcul, ** dans le cas d'une somme cumulée bidimensionnelle ** est la suivante. De plus, chaque carré est $ a [x] [y] $, et les suivants sont tous indexés à 0.
$ s [x] [y]: = [0, x) × [0, y) La somme des sections rectangulaires de $
Par conséquent, dans le cas du ** produit cumulatif bidimensionnel **, si cela se fait de la même manière, ce sera comme suit.
$ s [x] [y]: = [0, x) × [0, y) $ produit de sections rectangulaires
Par conséquent, ce ** produit cumulatif bidimensionnel peut être défini dans quatre directions **, et les trois autres sections rectangulaires sont les suivantes. L'expression de l'intervalle est différente de la définition des mathématiques, mais j'espère que vous pouvez comprendre l'atmosphère. (J'essayais de le faire dans une atmosphère sans décrire ce qui suit. ** Je vais décrire en détail la politique **.)
$ s [x] [y]: = [w-1, x) × [0, y) $ produit de sections rectangulaires
$ s [x] [y]: = [0, x) × [h-1, y) $ produit de sections rectangulaires
$ s [x] [y]: = [w-1, x) × [h-1, y) $ produit de sections rectangulaires
Si vous pouvez implémenter cela, vous pouvez écrire un programme en ** notant qu'il s'agit d'une section ouverte **. De plus, j'ai utilisé ma bibliothèque modint car je n'ai besoin de trouver que le reste divisé par 10 $ ^ 9 + 7 $.
Post-scriptum (8/2)
Diviser 0 en divisant la partie remplie du tout est gênant, il semble donc préférable de se rendre compte que ** le problème de trouver le produit de plusieurs nombres n'est exprimé que par le produit **.
C.cc
//Optimisation du compilateur
#pragma GCC optimize("Ofast")
//Inclure etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//macro
//pour boucle
//L'argument est(Variables dans la boucle,Amplitude de mouvement)Ou(Variables dans la boucle,Premier numéro,Nombre d'extrémités)、のどちらOu
//Les variables de boucle sans D sont incrémentées de 1 et les variables de boucle avec D sont décrémentées de 1.
//FORA est une gamme de déclaration(Si c'est difficile à utiliser, effacez-le)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//x est un conteneur tel que vector
#define ALL(x) x.begin(),x.end()
#define SIZE(x) ll(x.size())
//constant
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 100000 //10^5:Portée maximale de la baie
//Abréviation
#define PB push_back //Insérer
#define MP make_pair //constructeur de paires
#define F first //Le premier élément de paire
#define S second //Le deuxième élément de paire
template<ll mod> class modint{
public:
ll val=0;
//constructeur
modint(ll x=0){while(x<0)x+=mod;val=x%mod;}
//Copier le constructeur
modint(const modint &r){val=r.val;}
//Opérateur arithmétique
modint operator -(){return modint(-val);} //unaire
modint operator +(const modint &r){return modint(*this)+=r;}
modint operator -(const modint &r){return modint(*this)-=r;}
modint operator *(const modint &r){return modint(*this)*=r;}
modint operator /(const modint &r){return modint(*this)/=r;}
//Opérateur d'assignation
modint &operator +=(const modint &r){
val+=r.val;
if(val>=mod)val-=mod;
return *this;
}
modint &operator -=(const modint &r){
if(val<r.val)val+=mod;
val-=r.val;
return *this;
}
modint &operator *=(const modint &r){
val=val*r.val%mod;
return *this;
}
modint &operator /=(const modint &r){
ll a=r.val,b=mod,u=1,v=0;
while(b){
ll t=a/b;
a-=t*b;swap(a,b);
u-=t*v;swap(u,v);
}
val=val*u%mod;
if(val<0)val+=mod;
return *this;
}
//Opérateur de comparaison d'équivalence
bool operator ==(const modint& r){return this->val==r.val;}
bool operator <(const modint& r){return this->val<r.val;}
bool operator !=(const modint& r){return this->val!=r.val;}
};
using mint = modint<MOD>;
//Flux d'E / S
istream &operator >>(istream &is,mint& x){//N'ajoutez pas de const à x
ll t;is >> t;
x=t;
return (is);
}
ostream &operator <<(ostream &os,const mint& x){
return os<<x.val;
}
//Puissance
mint modpow(const mint &a,ll n){
if(n==0)return 1;
mint t=modpow(a,n/2);
t=t*t;
if(n&1)t=t*a;
return t;
}
signed main(){
//Code pour accélérer la saisie
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll h,w;cin>>h>>w;
vector<vector<ll>> A(h,vector<ll>(w,0));
REP(i,h)REP(j,w)cin>>A[i][j];
vector<vector<vector<mint>>> s(4,vector<vector<mint>>(h+1,vector<mint>(w+1,1)));
REP(j,h){
REP(k,w){
ll x,y;
x=j;y=k;
s[0][x+1][y+1]=s[0][x+1][y]*s[0][x][y+1]/s[0][x][y]*A[x][y];
}
}
REP(j,h){
REP(k,w-1){
ll x,y;
x=j;y=w-1-k;
s[1][x+1][y-1]=s[1][x+1][y]*s[1][x][y-1]/s[1][x][y]*A[x][y];
}
}
REP(j,h-1){
REP(k,w){
ll x,y;
x=h-1-j;y=k;
s[2][x-1][y+1]=s[2][x-1][y]*s[2][x][y+1]/s[2][x][y]*A[x][y];
}
}
REP(j,h-1){
REP(k,w-1){
ll x,y;
x=h-1-j;y=w-1-k;
s[3][x-1][y-1]=s[3][x-1][y]*s[3][x][y-1]/s[3][x][y]*A[x][y];
}
}
#if 0
REP(i,4){
REP(j,h){
REP(k,w){
cout<<s[i][j][k]<<" ";
}
cout<<endl;
}
cout<<endl;
}
#endif
ll q;cin>>q;
REP(_,q){
ll r,c;cin>>r>>c;
mint ans=1;
ll x,y;
x=r-1;y=c-1;
ans*=s[0][x][y];
//x=r;y=w-c;
ans*=s[1][x][y];
//x=h-r;y=c;
ans*=s[2][x][y];
//x=h-r;y=w-c;
ans*=s[3][x][y];
cout<<ans<<endl;
}
}
Recommended Posts