結果
| 問題 | No.315 世界のなんとか3.5 |
| ユーザー |
 snuke
|
| 提出日時 | 2015-12-09 01:05:11 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 254 ms / 2,000 ms |
| コード長 | 3,569 bytes |
| コンパイル時間 | 861 ms |
| コンパイル使用メモリ | 83,784 KB |
| 実行使用メモリ | 23,552 KB |
| 最終ジャッジ日時 | 2024-09-14 20:49:20 |
| 合計ジャッジ時間 | 5,583 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 36 |
ソースコード
#include <cstdio>#include <algorithm>#include <stack>#include <queue>#include <deque>#include <vector>#include <string>#include <string.h>#include <cstdlib>#include <ctime>#include <cmath>#include <map>#include <set>#include <iostream>#include <sstream>#include <numeric>#include <cctype>#define fi first#define se second#define rep(i,n) for(int i = 0; i < n; ++i)#define rrep(i,n) for(int i = 1; i <= n; ++i)#define drep(i,n) for(int i = n-1; i >= 0; --i)#define gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next)#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)#define rng(a) a.begin(),a.end()#define maxs(x,y) x = max(x,y)#define mins(x,y) x = min(x,y)#define pb push_back#define sz(x) (int)(x).size()#define pcnt __builtin_popcount#define snuke srand((unsigned)clock()+(unsigned)time(NULL));#define df(x) int x = in()using namespace std;typedef long long int ll;typedef pair<int,int> P;typedef vector<int> vi;typedef vector<vi> vvi;inline int in() { int x; scanf("%d",&x); return x;}inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}const int MX = 200005, INF = 1000010000;const ll LINF = 1000000000000000000ll;const double eps = 1e-10;// Mod intconst int mod = 1000000007;struct mint{ll x;mint():x(0){}mint(ll x):x((x%mod+mod)%mod){}mint operator+=(const mint& a){ if((x+=a.x)>=mod) x-=mod; return *this;}mint operator-=(const mint& a){ if((x+=mod-a.x)>=mod) x-=mod; return *this;}mint operator*=(const mint& a){ (x*=a.x)%=mod; return *this;}mint operator+(const mint& a)const{ return mint(*this) += a;}mint operator-(const mint& a)const{ return mint(*this) -= a;}mint operator*(const mint& a)const{ return mint(*this) *= a;}bool operator==(const mint& a)const{ return x == a.x;}};//int p;mint dp[MX][2][2][3];mint d[6][2][2][3][800];mint f(string s) {int n = sz(s);if (n < 6) {mint res = 0;int x = atoi(s.c_str());rep(i,x+1) {if (i%p == 0) continue;bool ok = false;if (i%3 == 0) ok = true;int y = i;while (y) {if (y%10 == 3) ok = true;y /= 10;}if (ok) res += 1;}return res;}rep(i,n+1)rep(j,2)rep(k,2)rep(h,3) dp[i][j][k][h] = 0;dp[0][0][0][0] = 1;rep(i,n)rep(j,2)rep(k,2)rep(h,3)rep(l,10) {int ni = i+1;int nj = j;int nk = k;int nh = (h*10+l)%3;if (nj == 0) {if (l > s[i]-'0') continue;if (l < s[i]-'0') nj = 1;}if (l == 3) nk = 1;dp[ni][nj][nk][nh] += dp[i][j][k][h];}rep(i,6)rep(j,2)rep(k,2)rep(h,3)rep(g,p) d[i][j][k][h][g] = 0;rep(j,2)rep(k,2)rep(h,3) d[0][j][k][h][0] = dp[n-5][j][k][h];rep(i,5)rep(j,2)rep(k,2)rep(h,3)rep(g,p)rep(l,10) {int ni = i+1;int nj = j;int nk = k;int nh = (h*10+l)%3;int ng = (g*10+l)%p;if (nj == 0) {if (l > s[n-5+i]-'0') continue;if (l < s[n-5+i]-'0') nj = 1;}if (l == 3) nk = 1;d[ni][nj][nk][nh][ng] += d[i][j][k][h][g];}mint res = 0;rep(j,2)rep(k,2)rep(h,3)rep(g,p) {if (g == 0) continue;if (k == 0 && h) continue;res += d[5][j][k][h][g];}return res;}mint g(string s) {int n = sz(s);int x = 0, y = 0;int cnt = 0;rep(i,n) {x = (x*10+s[i]-'0')%3;y = (y*10+s[i]-'0')%p;if (s[i] == '3') cnt++;}if (y == 0) return 0;if (cnt || x == 0) return 1;return 0;}int main() {string a, b;cin >> a >> b >> p;mint ans = f(b)-f(a)+g(a);cout<<ans.x<<endl;return 0;}