|
B - Login - Codeforces
直接模拟，库函数无法得到高精度答案。
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <stdio.h>
#define int long long
using namespace std;
const int mod = 1e9+7;
const int N = 1e3+10;
int ans[N];
signed main() {
int a,b,k;cin>>a>>b>>k;
if(a==b){
printf("1.");
while(k--){
printf("0");
}
return 0;
}
printf("0.");
while(k){
int t=0;
if(!a) break;
while(a<b){
a*=10;
t++;
}
if(k<t){
while(k--){
printf("0");
}
return 0;
}
k-=t;
t--;
while(t--){
printf("0");
}
if(k==0){
int ans = a/b;
a%=b;
a*=10;
if(a/b>=5){
ans++;
}
printf("%lld",ans);
}
else printf("%lld",a/b);
a%=b;
// if(!a) break;
}
while(k--){
printf("0");
}
return 0;
}
C -?Login - Codeforce
卡特兰数/逆元/递推算法「组合数学」
h(0)＝1(规定)，h(1)＝1，h(2)＝2，h(3)＝5，h(4)＝14，h(5)＝42，h(6)＝132，h(7)＝429，h(8)＝1430，h(9)＝4862，h(10)＝16796，h(11)＝58786，h(12)＝208012，h(13)＝742900，h(14)＝2674440
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <stdio.h>
#define int long long
using namespace std;
const int N=1e5+5;
const int mod=1e9+7;
int c[N],n,k,temp;
/*求逆元*/
int rev(int x)
{
int res=1,y=mod-2;
while(y)
{
if(y%2)
{
y--;
res=res*x%mod;
}
else
{
y/=2;
x=x*x%mod;
}
}
return res;
}
//快速mi
int qpow(int x,int p)
{
int res=1;
while(p)
{
if(p%2)
{
p--;
res=res*x%mod;
}
else
{
p/=2;
x=x*x%mod;
}
}
return res;
}
//计算卡特兰数
//2.Cn=（4*n-2）*C（n-1）/（n+1）
//
//3.Cn=C（2*n，n）/(n+1)
//
//4.Cn=C(2n,n)-C(2n,n-1)
void partktl(){
c[1]=2;
// int temp;
for(int i=2;i<=n;i++){
c[i] = ((((c[i-1]*(2*i)%mod)*(2*i-1)%mod)*rev(i)%mod)*rev(i)%mod)%mod;
}
temp=c[n];
temp = temp*rev(n+1)%mod;
// return temp;
}
signed main()
{
cin>>n>>k;
partktl();
printf("%lld",temp%mod*qpow(k, n)%mod);
return 0;
}
D -???????Login - Codeforces??????
读题，直接模拟就好
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <stdio.h>
#define int long long
using namespace std;
const int mod = 1e9+7;
signed main() {
int T;cin>>T;
while(T--)
{
string a;
cin>>a;
int flag=0,len=a.length();
for(int i=1;i<len;i++)
{
if(a[i]==a[i-1]);
else {
flag=1;
}
}
if(flag==0){
printf("%lld\n",len-1);
continue;
}else{
int cnt=0;
for(int i=1;i<len;i++){
if(a[0]!=a[i]){
cnt=i;
break;
}
}
printf("%lld\n",2*len-cnt);
}
}
return 0;
}
H -?Login - Codeforces
cnt{1-n}{n-2n}分别用来表示行和列
后面拓扑
#include <iostream>
#include <queue>
#include <string.h>
#include <cmath>
#include <algorithm>
#include <unordered_map>
#define int long long
using namespace std;
const int N = 1010;
int n,m,k;
int a[N][N],row[N],clo[N];
int str[N],stc[N],cnt[N*2],cntdd;
int read(){
int p=0,flag=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')
flag=-1;
c=getchar();
}
while(isdigit(c)){
p=(p<<3)+(p<<1)+(c^48);
c=getchar();
}
return p*flag;
}
bool topSort()
{
// 首先判断一下有没有只有一个的，如果啥问题都没有就更好了，就等着下一次搞
queue<int> q;
for(int i=1;i<=n;i++)
{
if(!cnt[i]) cntdd++;
if(cnt[i]==1) q.push(i);
if(!cnt[n+i]) cntdd++;
if(cnt[n+i]==1) q.push(n+i);
}
// 然后队内元素已经形成了一个顺序了
while(q.size())
{
int qq = q.front();
q.pop();cntdd++;
// 判断什么时候操作完了
// 操作完了就判断一下操作的对不对
if(cntdd >= 2*n) return true;
if(!cnt[qq]){
if(qq<=n){
if(str[qq]==row[qq]) continue;
else return false;
}
else{
if(stc[qq-n]==clo[qq-n]) continue;
else return false;
}
}
// 如果考虑行
if(qq<=n){
for(int i=1;i<=n;i++)
{
if(a[qq][i]!=-1) continue;
a[qq][i] = str[qq] ^ row[qq], str[qq] = row[qq];
cnt[n+i] --,stc[i] ^= a[qq][i];
if(cnt[n+i]==1) q.push(n+i);
break;
}
}
// 如果考虑列
else{
qq-=n;
for(int i=1;i<=n;i++)
{
if(a[i][qq]!=-1) continue;
a[i][qq] = stc[qq] ^ clo[qq], stc[qq] = clo[qq];
cnt[i] --,str[i] ^= a[i][qq];
if(cnt[i]==1) q.push(i);
break;
}
}
}
return false;
}
signed main() {
n=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{a[i][j]=read();if(a[i][j]==-1) cnt[i]++,cnt[n+j]++;else{str[i]^=a[i][j];stc[j]^=a[i][j];}}
for(int i=1;i<=n;i++) row[i]=read();
for(int j=1;j<=n;j++) clo[j]=read();
if(!topSort()){
printf("-1\n");
}else{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{printf("%lld",a[i][j]);if(j==n) printf("\n");else{printf(" ");}}
}
return 0;
}
I 晚些补
|