今日解いた問題たち②
つづきです。Solvedがだんだん減っていきます。
84B - Magical Array
数えるだけ。オーバーフローした。
#include<stdio.h> int a[100000]; int main(){ int b; scanf("%d",&b); for(int i=0;i<b;i++)scanf("%d",a+i); long long ret=0; int val=a[0]; long long re=1; for(int i=1;i<b;i++){ if(val!=a[i]){ ret+=re*(re+1)/2; val=a[i]; re=1; }else re++; } ret+=re*(re+1)/2; printf("%I64d\n",ret); }
288B - Polo the Penguin and Houses
埋め込む必要なさそうだけど埋め込んだ。b^(b-1)*(a-b)^(a-b)になるらしい。
#include<stdio.h> #include<algorithm> using namespace std; int key[]={1,2,9,64,625,7776,117649,2097152}; int main(){ int a,b; scanf("%d%d",&a,&b); long long ret=key[b-1]; int mod=1000000007; for(int i=0;i<a-b;i++)ret=ret*(a-b)%mod; printf("%I64d\n",ret); }
150B - Quantity of Strings
問題文が許されない。問題そのものもクソ。
#include<stdio.h> int main(){ int a,b,c; scanf("%d%d%d",&a,&b,&c); int mod=1000000007; long long ret=1; if(c>a||c==1){ for(int i=0;i<a;i++)ret=ret*b%mod; }else if(c==a){ for(int i=0;i<(a+1)/2;i++)ret=ret*b%mod; }else if(c%2==1){ ret=b*b; }else ret=b; printf("%d\n",ret); }
294C - Shaass and Lights
コンビネーション掛け算ゲー。
#include<stdio.h> #include<algorithm> using namespace std; int c[1000]; long long C[1001][1001]; int main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i<b;i++){ scanf("%d",c+i); } std::sort(c,c+b); int mod=1000000007; C[0][0]=1; for(int i=0;i<1000;i++) for(int j=0;j<=i;j++){ C[i+1][j]=(C[i+1][j]+C[i][j])%mod; C[i+1][j+1]=(C[i+1][j+1]+C[i][j])%mod; } long long ret=1; int n=a-b; for(int i=0;i<b-1;i++){ ret=ret*C[n][c[i+1]-c[i]-1]%mod; n-=c[i+1]-c[i]-1; for(int j=0;j<c[i+1]-c[i]-2;j++)ret=ret*2%mod; } ret=ret*C[n][c[0]-1]%mod; printf("%I64d\n",ret); }
204A - Little Elephant and Interval
こういう系の問題は難しすぎる。
#include<stdio.h> #include<algorithm> using namespace std; long long calc(long long a){ if(a<10LL)return a; if(a==10LL)return 9; long long t=1; long long ret=0; while(t<a){ if(t==10)ret+=t/10*9; else ret+=t/100*9; t*=10; } t/=10; //printf("%lld %lld\n",ret,t); for(int i=1;i<=9;i++){ if(t*i>a)break; if(t*(i+1)<a){ if(t==1)ret++; else ret+=t/10; }else{ if(a-i-t*i>=0LL)ret+=(a-i-t*i)/10+1; } } return ret; } int main(){ long long a,b; scanf("%I64d%I64d",&a,&b); printf("%I64d\n",calc(b)-calc(a-1)); }
285D - Permutation Sum
OEISを使うときはちゃんとどれが該当するかをしっかり調べましょう。
#include<stdio.h> int magic[]={1,0, 3,0, 15,0, 133,0, 2025,0, 37851,0, 1030367,0, 36362925,0, 1606008513,0}; int main(){ int a; int mod=1000000007; scanf("%d",&a); long long ret=magic[a-1]; for(int i=1;i<=a;i++){ ret=ret*i%mod; } printf("%d\n",(int)ret); }