Submission #2065094
Source Code Expand
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <list>
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;
#define PB push_back
#define MP make_pair
#define SZ(v) ((int)(v).size())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define REPE(i,n) FORE(i,0,n)
#define FORSZ(i,a,v) FOR(i,a,SZ(v))
#define REPSZ(i,v) REP(i,SZ(v))
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }
const int MOD=1000000007;
const int MAXDIM=100;
int pw(int x,int n) { int ret=1; while(true) { if(n&1) ret=(ll)ret*x%MOD; if((n>>=1)==0) return ret; x=(ll)x*x%MOD; } }
void inc(int &a,ll b) { a=(a+b)%MOD; }
void dec(int &a,ll b) { a=(a+MOD-b%MOD)%MOD; }
int solve1(int x,int X) {
int nx=X/x,ret=0;
inc(ret,x);
//printf("solve1(%d,%d)=%d\n",x,X,ret);
return ret;
}
int solve2(int x,int y,int X,int Y) {
int nx=X/x,ny=Y/y,ret=0;
inc(ret,(ll)pw(solve1(x,X),ny)*y);
inc(ret,(ll)pw(solve1(y,Y),nx)*x);
dec(ret,(ll)x*y);
//printf("solve2(%d,%d,%d,%d)=%d\n",x,y,X,Y,ret);
return ret;
}
int C[MAXDIM+1][MAXDIM+1];
int dp[MAXDIM+1][MAXDIM+1][MAXDIM+1]; // dp[cz][cx][cy] -> #ways for cz layers to have cx shifted rows and cy shifted columns
int solve3(int x,int y,int z,int X,int Y,int Z) {
if(X%x!=0||Y%y!=0||Z%z!=0) return 0;
int nx=X/x,ny=Y/y,nz=Z/z,ret=0;
// add solutions with 'cuts' using PIE
inc(ret,(ll)pw(solve2(x,y,X,Y),nz)*z);
inc(ret,(ll)pw(solve2(y,z,Y,Z),nx)*x);
inc(ret,(ll)pw(solve2(z,x,Z,X),ny)*y);
dec(ret,(ll)pw(solve1(x,X),ny*nz)*y*z);
dec(ret,(ll)pw(solve1(y,Y),nz*nx)*z*x);
dec(ret,(ll)pw(solve1(z,Z),nx*ny)*x*y);
inc(ret,(ll)x*y*z);
// add solutions with no 'cuts' -> pillars and layers
memset(dp,0,sizeof(dp)); dp[0][0][0]=1;
REP(cz,nz) REPE(cx,nx) REPE(cy,ny) {
int cdp=dp[cz][cx][cy]; if(cdp==0) continue;
inc(dp[cz+1][cx][cy],cdp); // nothing shifted in this layer
REPE(dx,nx-cx) { // rows shifted in this layer
int ways=pw(y,cx); if(dx==0) dec(ways,1);
ways=(ll)ways*pw(y-1,dx)%MOD;
ways=(ll)ways*C[nx-cx][dx]%MOD;
inc(dp[cz+1][cx+dx][cy],(ll)cdp*ways);
}
REPE(dy,ny-cy) { // cols shifted in this layer
int ways=pw(x,cy); if(dy==0) dec(ways,1);
ways=(ll)ways*pw(x-1,dy)%MOD;
ways=(ll)ways*C[ny-cy][dy]%MOD;
inc(dp[cz+1][cx][cy+dy],(ll)cdp*ways);
}
}
FORE(cx,1,nx-1) FORE(cy,1,ny-1) {
int cdp=dp[nz][cx][cy]; if(cdp==0) continue;
int npillars=(nx-cx)*(ny-cy);
int ways=pw(z,npillars); dec(ways,1);
ways=(ll)ways*x*y*z%MOD;
inc(ret,(ll)cdp*ways);
}
return ret;
}
int x,y,z,X,Y,Z;
void run() {
REPE(i,MAXDIM) { C[i][0]=C[i][i]=1; FOR(j,1,i) C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD; }
scanf("%d%d%d%d%d%d",&x,&y,&z,&X,&Y,&Z);
printf("%d\n",solve3(x,y,z,X,Y,Z));
}
int main() {
run();
return 0;
}
Submission Info
Submission Time
2018-02-04 23:52:47+0900
Task
J - Rectangles
User
krijgertje
Language
C++14 (GCC 5.4.1)
Score
2100
Code Size
3170 Byte
Status
AC
Exec Time
536 ms
Memory
4352 KB
Compile Error
./Main.cpp: In function ‘void run()’:
./Main.cpp:103:41: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d%d%d",&x,&y,&z,&X,&Y,&Z);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
2100 / 2100
Status
Set Name
Test Cases
Sample
0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt
All
0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt, 1_036.txt, 1_037.txt, 1_038.txt, 1_039.txt, 1_040.txt, 1_041.txt, 1_042.txt, 1_043.txt, 1_044.txt, 1_045.txt, 1_046.txt, 1_047.txt, 1_048.txt, 1_049.txt, 1_050.txt, 1_051.txt, 1_052.txt, 1_053.txt, 1_054.txt, 1_055.txt, 1_056.txt, 1_057.txt, 1_058.txt, 1_059.txt, 1_060.txt, 1_061.txt, 1_062.txt, 1_063.txt, 1_064.txt, 1_065.txt, 1_066.txt, 1_067.txt, 1_068.txt, 1_069.txt, 1_070.txt, 1_071.txt, 1_072.txt, 1_073.txt, 1_074.txt, 1_075.txt, 1_076.txt, 1_077.txt, 1_078.txt, 1_079.txt, 1_080.txt, 1_081.txt, 1_082.txt, 1_083.txt, 1_084.txt, 1_085.txt, 1_086.txt
Case Name
Status
Exec Time
Memory
0_000.txt
AC
3 ms
4352 KB
0_001.txt
AC
3 ms
4352 KB
0_002.txt
AC
1 ms
256 KB
0_003.txt
AC
64 ms
4352 KB
1_004.txt
AC
12 ms
4352 KB
1_005.txt
AC
35 ms
4352 KB
1_006.txt
AC
6 ms
4352 KB
1_007.txt
AC
4 ms
4352 KB
1_008.txt
AC
3 ms
4352 KB
1_009.txt
AC
44 ms
4352 KB
1_010.txt
AC
23 ms
4352 KB
1_011.txt
AC
3 ms
4352 KB
1_012.txt
AC
30 ms
4352 KB
1_013.txt
AC
16 ms
4352 KB
1_014.txt
AC
3 ms
4352 KB
1_015.txt
AC
45 ms
4352 KB
1_016.txt
AC
24 ms
4352 KB
1_017.txt
AC
3 ms
4352 KB
1_018.txt
AC
536 ms
4352 KB
1_019.txt
AC
265 ms
4352 KB
1_020.txt
AC
3 ms
4352 KB
1_021.txt
AC
19 ms
4352 KB
1_022.txt
AC
11 ms
4352 KB
1_023.txt
AC
3 ms
4352 KB
1_024.txt
AC
31 ms
4352 KB
1_025.txt
AC
17 ms
4352 KB
1_026.txt
AC
3 ms
4352 KB
1_027.txt
AC
20 ms
4352 KB
1_028.txt
AC
11 ms
4352 KB
1_029.txt
AC
3 ms
4352 KB
1_030.txt
AC
3 ms
4352 KB
1_031.txt
AC
3 ms
4352 KB
1_032.txt
AC
3 ms
4352 KB
1_033.txt
AC
3 ms
4352 KB
1_034.txt
AC
3 ms
4352 KB
1_035.txt
AC
4 ms
4352 KB
1_036.txt
AC
3 ms
4352 KB
1_037.txt
AC
3 ms
4352 KB
1_038.txt
AC
3 ms
4352 KB
1_039.txt
AC
3 ms
4352 KB
1_040.txt
AC
3 ms
4352 KB
1_041.txt
AC
3 ms
4352 KB
1_042.txt
AC
3 ms
4352 KB
1_043.txt
AC
3 ms
4352 KB
1_044.txt
AC
3 ms
4352 KB
1_045.txt
AC
3 ms
4352 KB
1_046.txt
AC
3 ms
4352 KB
1_047.txt
AC
3 ms
4352 KB
1_048.txt
AC
3 ms
4352 KB
1_049.txt
AC
3 ms
4352 KB
1_050.txt
AC
3 ms
4352 KB
1_051.txt
AC
3 ms
4352 KB
1_052.txt
AC
3 ms
4352 KB
1_053.txt
AC
3 ms
4352 KB
1_054.txt
AC
3 ms
4352 KB
1_055.txt
AC
3 ms
4352 KB
1_056.txt
AC
3 ms
4352 KB
1_057.txt
AC
1 ms
256 KB
1_058.txt
AC
1 ms
256 KB
1_059.txt
AC
1 ms
256 KB
1_060.txt
AC
1 ms
256 KB
1_061.txt
AC
1 ms
256 KB
1_062.txt
AC
1 ms
256 KB
1_063.txt
AC
1 ms
256 KB
1_064.txt
AC
1 ms
256 KB
1_065.txt
AC
1 ms
256 KB
1_066.txt
AC
1 ms
256 KB
1_067.txt
AC
3 ms
4352 KB
1_068.txt
AC
6 ms
4352 KB
1_069.txt
AC
3 ms
4352 KB
1_070.txt
AC
3 ms
4352 KB
1_071.txt
AC
19 ms
4352 KB
1_072.txt
AC
3 ms
4352 KB
1_073.txt
AC
3 ms
4352 KB
1_074.txt
AC
3 ms
4352 KB
1_075.txt
AC
3 ms
4352 KB
1_076.txt
AC
3 ms
4352 KB
1_077.txt
AC
3 ms
4352 KB
1_078.txt
AC
4 ms
4352 KB
1_079.txt
AC
3 ms
4352 KB
1_080.txt
AC
3 ms
4352 KB
1_081.txt
AC
4 ms
4352 KB
1_082.txt
AC
4 ms
4352 KB
1_083.txt
AC
3 ms
4352 KB
1_084.txt
AC
3 ms
4352 KB
1_085.txt
AC
5 ms
4352 KB
1_086.txt
AC
3 ms
4352 KB