結果

問題 No.315 世界のなんとか3.5
ユーザー piyoko_212
提出日時 2015-12-25 17:36:20
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 673 ms / 2,000 ms
コード長 2,659 bytes
コンパイル時間 342 ms
コンパイル使用メモリ 37,968 KB
実行使用メモリ 32,592 KB
最終ジャッジ日時 2024-09-18 23:54:17
合計ジャッジ時間 9,398 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 36
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:91:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   91 |         scanf("%s%s%d",A,B,&P);
      |         ~~~~~^~~~~~~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
long long mod=1000000007;
char str[210000];
char A[210000];
char B[210000];
int P;
int m3[110000];
int y[110000];
int cnt[2][3];
int lim=1000;
long long dp[210000][3][2][3];
int las=0;
char tmp[10];
long long count(int t){
    for(int i=0;i<210000;i++)for(int j=0;j<3;j++)for(int k=0;k<2;k++)for(int l=0;l<3;l++)
        dp[i][j][k][l]=0;
    for(int i=1;i<10;i++){
        dp[1][i%3][i==3][(i==(str[0]-'0'))?0:((i>(str[0]-'0'))?2:1)]++;
    }
    int len=strlen(str);
    for(int i=1;i<len-las;i++){
    //printf("%c\n",str[i]);
        for(int j=0;j<3;j++)for(int k=0;k<2;k++)for(int l=0;l<3;l++){
            if(!dp[i][j][k][l])continue;
            for(int m=0;m<10;m++){
                int tj=j;
                int tk=k;
                int tl=l;
                tj=(tj+m)%3;
                if(m==3)tk=1;
                if(tl==0){
                    if(m<str[i]-'0')tl=1;
                    if(m>str[i]-'0')tl=2;
                }
            //  if(l==0)printf("%d %d %d %d %d %d %d %d\n",i,j,k,l,m,tj,tk,tl);
                dp[i+1][tj][tk][tl]=(dp[i+1][tj][tk][tl]+dp[i][j][k][l])%mod;
            }
        }
    }
    long long ret=0;
    if(len>las){
        for(int i=len-las;i<len;i++)tmp[i-len+las]=str[i];
        int b;
        sscanf(tmp,"%d",&b);
    //  printf("%d\n",b);
        ret+=cnt[0][0]+cnt[1][0]+cnt[1][1]+cnt[1][2];
    //  printf("%lld\n",ret);
        for(int i=1;i<=len-las;i++){
            for(int j=0;j<3;j++){
                for(int k=0;k<2;k++){
                    for(int l=0;l<3;l++){
                        if(!dp[i][j][k][l])continue;
                        //printf("%d %d %d %d: %lld\n",i,j,k,l,dp[i][j][k][l]);
                        if(i==len-las&&l==2)continue;
                        if(i==len-las&&l==0){
                            long long tt=0;
                            for(int m=0;m<=b;m++){
                                if(m%P==0)continue;
                                if(t==1&&m==b)continue;
                                if((m3[m]+j)%3==0||y[m]||k)tt++;
                            }
                    //      printf("%lld\n",tt);
                            ret=(ret+tt*dp[i][j][k][l])%mod;
                    //      printf("%lld\n",ret);
                        }else{
                            if(k==1)ret=(ret+dp[i][j][k][l]*(cnt[1][0]+cnt[1][1]+cnt[1][2]+cnt[0][0]+cnt[0][1]+cnt[0][2]))%mod;
                            else ret=(ret+dp[i][j][k][l]*(cnt[1][0]+cnt[1][1]+cnt[1][2]+cnt[0][(3-j)%3]))%mod;
                //          printf("%lld\n",ret);
                        }
                    }
                }
            }
        }
    }else{
        int b;
        sscanf(str,"%d",&b);
        for(int i=0;i<=b;i++){
            if(i%P==0)continue;
            if(t==1&&i==b)continue;
            if(m3[i]==0||y[i])ret++;
        }
    }
    ret%=mod;
    //printf("%lld\n",ret);
    return ret;
}
int main(){
    scanf("%s%s%d",A,B,&P);
    las=3;
    if(P>10){lim*=10;las++;}
    if(P>100){lim*=10;las++;}
    for(int i=0;i<lim;i++){
        int X=0;
        int Y=0;
        if(i%P==0)continue;
        int z=i;
        while(z){
            X+=z%10;
            if(z%10==3)Y=1;
            z/=10;
        }
        X%=3;
        m3[i]=X;y[i]=Y;cnt[Y][X]++;
    }
    long long ret=0;
    for(int i=0;i<210000;i++)str[i]=B[i];
    ret=count(0);
    for(int i=0;i<210000;i++)str[i]=A[i];
    ret=(ret+mod-count(1))%mod;
    printf("%lld\n",ret);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0